Collaborative Research: AF: Small: Structural Graph Algorithms via General Frameworks

合作研究：AF：小型：通过通用框架的结构图算法

• 批准号: 2347321
• 负责人: Erik Demaine
• 金额: $ 30万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-04-15 至 2027-03-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2347321&HistoricalAwards=false
• 关键词: Collaborative; Research; AF; Small; Structural

Networks are everywhere, from gene regulatory networks, brain networks, and health/disease networks, to online social networks. This project will develop frameworks for algorithms to better understand, analyze, and manipulate such networks. The resulting algorithms will provide provable guarantees on both how much computation time they require and on the quality of the computed solution, enabling new analysis tools for real-world networks. The researchers will also co-develop a new graduate course about network algorithms and the underlying technologies of fixed-parameter algorithms, approximation algorithms, and algorithmic graph theory. The investigators plan to publish a textbook on the topics covered in this project to further their educational impact.Instead of developing individual algorithmic solutions to a specific problem (the typical approach in the field of algorithms), this project will develop very general algorithmic frameworks that apply to an entire category of problems all at once. In this way, the investigators approach a general theory of graph algorithms, wherein a given problem of interest can simply be adapted into the general approach. The project considers the two main types of algorithms for solving NP-hard graph optimization problems. Approximation algorithms allow the result to be a small factor away from the optimal, but still requires polynomial time. Parameterized algorithms allow the running time to be exponential, but only with respect to a parameter other than the problem size, while the result must be optimal.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.

网络无处不在，从基因调控网络、大脑网络、健康/疾病网络到在线社交网络。该项目将开发算法框架，以更好地理解、分析和操纵此类网络。由此产生的算法将为所需的计算时间和计算解决方案的质量提供可证明的保证，从而为现实世界的网络提供新的分析工具。研究人员还将共同开发一门新的研究生课程，内容涉及网络算法以及固定参数算法、近似算法和算法图论的底层技术。研究人员计划就该项目所涵盖的主题出版一本教科书，以进一步扩大其教育影响。该项目将开发非常通用的算法框架，而不是针对特定问题开发单独的算法解决方案（算法领域的典型方法）。一次性适用于整个类别的问题。 通过这种方式，研究人员研究了图算法的一般理论，其中给定的感兴趣问题可以简单地适应一般方法。 该项目考虑了解决 NP 难图优化问题的两种主要算法。 近似算法允许结果与最优结果相差很小，但仍然需要多项式时间。参数化算法允许运行时间呈指数增长，但仅限于问题规模以外的参数，而结果必须是最优的。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值进行评估，认为值得支持以及更广泛的影响审查标准。