AF: Small: Flows, Cuts, Treewidth and Algorithms for Routing, Network Design and Related Problems

AF：小：流、割、树宽和路由算法、网络设计及相关问题

• 批准号: 1319376
• 负责人: Chandra Chekuri
• 金额: $ 49.52万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1319376&HistoricalAwards=false
• 关键词: AF; Small; Flows; Cuts; Treewidth

Graphs and networks are of fundamental importance in discrete optimization. Several natural graph optimization problems are NP-Hard and a large body of work has been devoted to designing and analyzing approximation algorithms for these problems. Key algorithmic advances are tied to structural understanding of graphs and mathematical programming relaxations. This research has resulted in effective heuristics as well as exciting connections with different areas of mathematics. In this award, the PI will study approximation algorithms for graph optimization problems in two broad areas: multicommodity flow and cut problems in routing, and connectivity problems in network design. Some specific problems of interest are:(i) Maximum disjoint paths, congestion minimization and relation between integer flows, fractional flows and cuts. In particular, node-capacitated undirected graphs and directed graphs with symmetric demands will be the emphasis.(ii) Treewidth decomposition theorems and applications to fixed parameter tractability and Erdos-Posa theorems, in particular in directed graphs.(iii) The survivable network design problem with vertex connectivity requirements.The proposed problems on flows, cuts and network design are at the core of combinatorial optimization and approximation algorithms research. Progress on these problems will require advances in algorithms and structural understanding of graphs, in particular directed graphs, which will have several auxiliary benefits. The project will support and train two to three PhD students in the design and analysis of algorithms at the University of Illinois at Urbana-Champaign. The PI plans to write a survey outlining the recent developments on algorithms for routing, and their connection to graph theoretical results on treewidth.

图和网络在离散优化中至关重要。 一些自然图优化问题是 NP-Hard 问题，并且大量工作致力于设计和分析这些问题的近似算法。关键算法的进步与对图的结构理解和数学编程松弛有关。这项研究产生了有效的启发式方法以及与不同数学领域的令人兴奋的联系。 在该奖项中，PI 将研究两个广泛领域的图优化问题的近似算法：路由中的多商品流和切割问题以及网络设计中的连接问题。一些感兴趣的具体问题是：（i）最大不相交路径、拥塞最小化以及整数流、分数流和割断之间的关系。特别是，节点容量无向图和具有对称需求的有向图将成为重点。(ii) 树宽分解定理及其在固定参数易处理性和 Erdos-Posa 定理中的应用，特别是在有向图中。(iii) 可生存网络设计顶点连通性要求问题。所提出的流、割和网络设计问题是组合优化和近似算法研究的核心。这些问题的进展需要算法和对图（特别是有向图）的结构理解的进步，这将带来一些辅助好处。 该项目将支持和培训伊利诺伊大学厄巴纳-香槟分校的两到三名算法设计和分析博士生。 PI 计划撰写一份调查报告，概述路由算法的最新进展，以及它们与树宽图理论结果的联系。