AF: Small: Algorithms for Graph Cuts

AF：小：图割算法

• 批准号: 2329230
• 负责人: Debmalya Panigrahi
• 金额: $ 30万
• 依托单位: Duke University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-11-01 至 2026-10-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2329230&HistoricalAwards=false
• 关键词: AF; Small; Algorithms; Graph; Cuts

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 的法定使命，并通过使用基金会的智力优点和更广泛的影响审查标准进行评估，被认为值得支持。