AF: Small: Algorithms for Graph Cuts
AF:小:图割算法
基本信息
- 批准号:2329230
- 负责人:
- 金额:$ 30万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2023
- 资助国家:美国
- 起止时间:2023-11-01 至 2026-10-31
- 项目状态:未结题
- 来源:
- 关键词:
项目摘要
Graphs are ubiquitous in nature and in the sciences, and model a broad array of objects and activities ranging from telecommunication and transportation networks to social interactions to biological and artificial neural networks. Unsurprisingly, the algorithmic study of graphs has a long history tracing back to the earliest days of computer science; today, graph algorithms are routinely used in applications ranging from online maps to medical imaging to VLSI design. Fundamentally, graphs connect entities, and many of the core questions in graph algorithms seek to understand how robust or fragile these connections are in the presence of link failures. This project aims to design new algorithms that are faster, simpler, and help better understand the connectivity properties of a graph. The newly designed algorithms have the potential of significant real-world impact in areas such as image segmentation and design of reliable networks. On the educational front, the project will train graduate and undergraduate students, with an emphasis on participation of underrepresented groups.The project has two main thrusts: the design of deterministic algorithms for graph cuts and the study of graph connectivity under random edge failures. Over the last few decades, progress in problems such as minimum cut has largely been driven by the design of new (Monte Carlo) randomized algorithms. These algorithms, while often very elegant and highly efficient, suffer from the shortcoming that they provide answers that are inconsistent across multiple runs, and that are occasionally incorrect. This prevents their use in many downstream applications, both in theory and practice. The first thrust of the project is to design derandomization tools that help bridge the gap between the best randomized and deterministic algorithms for fundamental graph connectivity problems. The second thrust is motivated by the observation that in many practical scenarios, edge failures are random, rather than adversarial, events. Traditional graph connectivity measures such as minimum cuts do not provide a faithful estimate of the resilience of a network to such random failures. The project aims to design new paradigms and algorithms to study connectivity properties in networks that are subject to random edge failures.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
图在自然界和科学中无处不在,并且对从电信和交通网络到社会交互到生物和人工神经网络的各种对象和活动进行建模。毫不奇怪,图的算法研究有着悠久的历史,可以追溯到计算机科学的早期;今天,图算法经常用于从在线地图到医学成像到VLSI设计的应用中。从根本上说,图连接实体,图算法中的许多核心问题都试图了解这些连接在链路故障的情况下有多健壮或脆弱。该项目旨在设计更快,更简单的新算法,并帮助更好地理解图的连通性。新设计的算法在图像分割和可靠网络设计等领域具有重要的现实影响力。在教育方面,该项目将培训研究生和本科生,重点是代表性不足的群体的参与。该项目有两个主要目标:设计图切割的确定性算法和研究随机边缘故障下的图连通性。在过去的几十年里,最小割等问题的进展在很大程度上是由新的(蒙特卡罗)随机算法的设计推动的。这些算法虽然通常非常优雅和高效,但它们的缺点是它们提供的答案在多次运行中不一致,并且偶尔不正确。这在理论和实践上都阻止了它们在许多下游应用中的使用。该项目的第一个目标是设计去随机化工具,帮助弥合基本图连通性问题的最佳随机算法和确定性算法之间的差距。第二个目标的动机是观察到在许多实际场景中,边缘故障是随机的,而不是对抗性的事件。传统的图连通性度量(如最小割)无法准确估计网络对此类随机故障的弹性。该项目旨在设计新的范例和算法,以研究网络中的连通性,受到随机边缘故障。该奖项反映了NSF的法定使命,并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Debmalya Panigrahi其他文献
Beyond the Quadratic Time Barrier for Network Unreliability
超越网络不可靠性的二次时间障碍
- DOI:
10.48550/arxiv.2304.06552 - 发表时间:
2023 - 期刊:
- 影响因子:0
- 作者:
Ruoxu Cen;W. He;Jason Li;Debmalya Panigrahi - 通讯作者:
Debmalya Panigrahi
2 A Primal-Dual Algorithm for Steiner Forest
2 Steiner森林的原对偶算法
- DOI:
- 发表时间:
2019 - 期刊:
- 影响因子:0
- 作者:
Debmalya Panigrahi;Kevin Sun - 通讯作者:
Kevin Sun
Online Node-Weighted Steiner Forest and Extensions via Disk Paintings
在线节点加权斯坦纳森林和通过磁盘绘画的扩展
- DOI:
- 发表时间:
2013 - 期刊:
- 影响因子:0
- 作者:
M. Hajiaghayi;Vahid Liaghat;Debmalya Panigrahi - 通讯作者:
Debmalya Panigrahi
Random Contractions and Sampling for Hypergraph and Hedge Connectivity
超图和对冲连接的随机收缩和采样
- DOI:
- 发表时间:
2017 - 期刊:
- 影响因子:0
- 作者:
M. Ghaffari;David R Karger;Debmalya Panigrahi - 通讯作者:
Debmalya Panigrahi
Near-Optimal Online Algorithms for Prize-Collecting Steiner Problems
收奖斯坦纳问题的近最优在线算法
- DOI:
10.1007/978-3-662-43948-7_48 - 发表时间:
2014 - 期刊:
- 影响因子:0
- 作者:
M. Hajiaghayi;Vahid Liaghat;Debmalya Panigrahi - 通讯作者:
Debmalya Panigrahi
Debmalya Panigrahi的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Debmalya Panigrahi', 18)}}的其他基金
Conference: Workshop on Learning-augmented Algorithms
会议:学习增强算法研讨会
- 批准号:
2239610 - 财政年份:2022
- 资助金额:
$ 30万 - 项目类别:
Standard Grant
Collaborative Research: AF: Medium: Algorithms Meet Machine Learning: Mitigating Uncertainty in Optimization
协作研究:AF:媒介:算法遇见机器学习:减轻优化中的不确定性
- 批准号:
1955703 - 财政年份:2020
- 资助金额:
$ 30万 - 项目类别:
Continuing Grant
CAREER: New Directions in Graph Algorithms
职业:图算法的新方向
- 批准号:
1750140 - 财政年份:2018
- 资助金额:
$ 30万 - 项目类别:
Continuing Grant
AF: Small: Allocation Algorithms in Online Systems
AF:小型:在线系统中的分配算法
- 批准号:
1527084 - 财政年份:2015
- 资助金额:
$ 30万 - 项目类别:
Standard Grant
相似国自然基金
昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
- 批准号:
- 批准年份:2024
- 资助金额:0.0 万元
- 项目类别:省市级项目
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
- 批准号:n/a
- 批准年份:2022
- 资助金额:10.0 万元
- 项目类别:省市级项目
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
- 批准号:32000033
- 批准年份:2020
- 资助金额:24.0 万元
- 项目类别:青年科学基金项目
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
- 批准号:31972324
- 批准年份:2019
- 资助金额:58.0 万元
- 项目类别:面上项目
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
- 批准号:81900988
- 批准年份:2019
- 资助金额:21.0 万元
- 项目类别:青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
- 批准号:31870821
- 批准年份:2018
- 资助金额:56.0 万元
- 项目类别:面上项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
- 批准号:31802058
- 批准年份:2018
- 资助金额:26.0 万元
- 项目类别:青年科学基金项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
- 批准号:31772128
- 批准年份:2017
- 资助金额:60.0 万元
- 项目类别:面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
- 批准号:81704176
- 批准年份:2017
- 资助金额:20.0 万元
- 项目类别:青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
- 批准号:91640114
- 批准年份:2016
- 资助金额:85.0 万元
- 项目类别:重大研究计划
相似海外基金
Collaborative Research: AF: Small: Structural Graph Algorithms via General Frameworks
合作研究:AF:小型:通过通用框架的结构图算法
- 批准号:
2347322 - 财政年份:2024
- 资助金额:
$ 30万 - 项目类别:
Standard Grant
AF: Small: Communication-Aware Algorithms for Dynamic Allocation of Heterogeneous Resources
AF:小型:用于异构资源动态分配的通信感知算法
- 批准号:
2335187 - 财政年份:2024
- 资助金额:
$ 30万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Structural Graph Algorithms via General Frameworks
合作研究:AF:小型:通过通用框架的结构图算法
- 批准号:
2347321 - 财政年份:2024
- 资助金额:
$ 30万 - 项目类别:
Standard Grant
AF: Small: New Challenges and Approaches in Clustering Algorithms
AF:小:聚类算法的新挑战和方法
- 批准号:
2311397 - 财政年份:2023
- 资助金额:
$ 30万 - 项目类别:
Standard Grant
AF: Small: RUI: Toward High-Performance Block Krylov Subspace Algorithms for Solving Large-Scale Linear Systems
AF:小:RUI:用于求解大规模线性系统的高性能块 Krylov 子空间算法
- 批准号:
2327619 - 财政年份:2023
- 资助金额:
$ 30万 - 项目类别:
Standard Grant
SHF: AF: Small: Algorithms and a Code Generator for Faster Stencil Computations
SHF:AF:Small:用于更快模板计算的算法和代码生成器
- 批准号:
2318633 - 财政年份:2023
- 资助金额:
$ 30万 - 项目类别:
Standard Grant
NSF-BSF: AF: Small: Algorithms for Graph-Based Codes
NSF-BSF:AF:小型:基于图形的代码算法
- 批准号:
2133154 - 财政年份:2022
- 资助金额:
$ 30万 - 项目类别:
Standard Grant
AF: Small: Towards New Relaxations for Online Algorithms
AF:小:在线算法的新放松
- 批准号:
2224718 - 财政年份:2022
- 资助金额:
$ 30万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Foundations of Algorithms Augmented with Predictions
合作研究:AF:小型:预测增强的算法基础
- 批准号:
2121745 - 财政年份:2022
- 资助金额:
$ 30万 - 项目类别:
Standard Grant