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.
