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

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

• 批准号: 2347322
• 负责人: Mohammad Hajiaghayi
• 金额: $ 30万
• 依托单位: University of Maryland, College Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-04-15 至 2027-03-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2347322&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-HARD图优化问题的两种主要类型。 近似算法允许结果远离最佳因素，但仍然需要多项式时间。参数化算法允许运行时间是指数级的，但仅在问题大小以外的其他参数方面，而结果必须是最佳的。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的智力优点和更广泛影响的审查标准来评估的支持。