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）可生存的网络设计设计。顶点连通性要求的问题。流动，削减和网络设计上的拟议问题是组合优化和近似算法研究的核心。这些问题的进展将需要算法和对图的结构理解的进步，特别是有向图，这将具有多种辅助益处。 该项目将在伊利诺伊大学Urbana-Champaign大学的算法设计和分析中支持并培训两到三名博士学位学生。 PI计划撰写一项调查，概述了有关路由算法的最新发展，以及它们与树宽方面的理论结果的联系。