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困难的，大量的工作已经致力于设计和分析这些问题的近似算法。关键的算法进步与图的结构理解和数学规划松弛有关。这项研究产生了有效的启发，并与数学的不同领域建立了令人兴奋的联系。在该奖项中，PI将研究两大领域图优化问题的近似算法：路由中的多商品流和切割问题，以及网络设计中的连接问题。研究的具体问题有：(1)最大不相交路径、拥塞最小化以及整数流、分数流和切点之间的关系。特别是，节点容量无向图和有向图的对称需求将是重点。（ii）树宽分解定理及其在固定参数可追溯性和Erdos-Posa定理中的应用，特别是在有向图中的应用。（iii）具有顶点连接要求的可生存网络设计问题。提出的流、切和网络设计问题是组合优化和逼近算法研究的核心。在这些问题上取得进展将需要在算法和图的结构理解方面取得进展，特别是有向图，这将有几个辅助的好处。该项目将在伊利诺伊大学厄巴纳-香槟分校支持和培训两到三名算法设计和分析方面的博士生。PI计划撰写一份调查报告，概述路由算法的最新发展，以及它们与树宽图理论结果的联系。