Approximation Algorithms for Routing and Network Design

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

The goal of this project is to obtain new algorithms and insights for some fundamental problems in graphs and networks with a focus on routing and network design. A prototypical question in routing is to find paths that connect a given set of source-destination pairs while obeying the link and node capacity constraints of an underlying network. Similarly, a prototypical question in network design is to build a minimum cost network to support a given communication pattern. Problems in these two areas are at the core of combinatorial optimization with many applications. They also play a crucial role in the development of algorithms and structural graph theory. The problems considered in this project are NP-hard and the approach is to obtain polynomial time approximation algorithms as well as bounds on the integrality gaps of linear programming based relaxations. Questions central to the agenda are disjoint paths problems in undirected graphs, buy-at-bulk network design, and orienteering. In addition to improved algorithms for these and related problems, new broadly applicable algorithmic techniques are expected to be discovered. There are several applications that can directly benefit including VLSI design, bandwidth and resource allocation in networks, design of optical networks, and vehicle routing. The project will support and train PhD students and help in the dissemination of advanced algorithmic ideas via new classes and lecture notes.