The goal of this project is to study the computational tractability of fundamental network optimization problems such as disjoint paths, congestion minimization, and multicut. For instance, given a network, and a collection of source-destination pairs, how does one route each source to its destination without causing congestion? What is a smallest set of network links whose failure disconnects each source from its destination? These optimization problems are intimately related to each other via the dual notions of cuts and flows in a network. Taken together, they are among the most widely studied combinatorial optimization problems, and are intrinsic to many applications in computer science. It is no surprise that the study of these problems is connected to major developments in algorithms design, hardness of approximation, and graph theory.
The network optimization problems above are NP-hard even in simple settings. This project aims to advance understanding of the polynomial-time approximability of these fundamental optimization problems as well as gain new insights into relationships among multicommodity flows, cuts, and integral routings. This research will focus on new algorithmic techniques as well as new hardness and integrality gap constructions that give insights into the combinatorial structure of these problems. Although these problems are foundational in nature, they are directly related to applications in network design and routing, and resource allocation. Results obtained from this research will be integrated in an advanced course on combinatorial optimization. The project will also help support and train a graduate student, as well as research projects for undergraduates.
This project studied the computational tractability of several fundamental optimization problems on graphs. Some examples of problems considered in this project include the disjoint paths problem, the multicut problem, survivable network design, and the bipartite matching problem. For instance, given a network, and a collection of source-destination pairs, how does one route each source to its destination without causing congestion? What is a smallest set of network links whose failure disconnects each source from its destination? How fast can one compute an assignment of jobs to machines so that each job is assigned to exactly one machine and each machine is assigned exactly one job? These optimization problems are closely related to each other and are intrinsic to many applications in computer science. The research supported by this project has led to efficient new algorithms for some of the problems described above, while for some others, it has established formal barriers to efficiently obtaining near-optimal solutions. These results have been published in leading peer-reviewed conferences and journals in theoretical computer science. This project has also helped support mentoring and training of an undergraduate student, and three graduate students whose PhD dissertation research is connected to topics considered in this project. Finally, in course of this project, the PI gave several lectures to high-school students on algorithmic thinking and its applications in computer science and related disciplines.
