Cuts, Flows, and Network Routing

University Of Pennsylvania, Philadelphia PA

Investigators

Abstract

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.