Approximation Algorithms for Routing and Network Design

点击翻译按钮获取中文摘要

The goal of this project is to obtain new algorithms and insights forsome fundamental problems in graphs and networks with a focus onrouting and network design. A prototypical question in routing is tofind paths that connect a given set of source-destination pairs whileobeying the link and node capacity constraints of an underlyingnetwork. Similarly, a prototypical question in network design is tobuild a minimum cost network to support a given communicationpattern. Problems in these two areas are at the core of combinatorialoptimization with many applications. They also play a crucial role inthe development of algorithms and structural graph theory.The problems considered in this project are NP-hard and the approachis to obtain polynomial time approximation algorithms as well asbounds on the integrality gaps of linear programming basedrelaxations. Questions central to the agenda are disjoint pathsproblems in undirected graphs, buy-at-bulk network design, andorienteering. In addition to improved algorithms for these andrelated problems, new broadly applicable algorithmic techniques areexpected to be discovered. There are several applications that candirectly benefit including VLSI design, bandwidth and resourceallocation in networks, design of optical networks, and vehiclerouting. The project will support and train PhD students and help inthe dissemination of advanced algorithmic ideas via new classes andlecture notes.