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

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

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.