Approximation Algorithms for Routing and Network Design

这个项目的目标是获得新的算法和见解的一些基本问题的图和网络，重点是路由和网络设计。路由选择中的一个典型问题是找到连接一组给定的源-目的地对的路径，同时遵守底层网络的链路和节点容量约束。 同样，网络设计中的一个典型问题是建立一个最小成本的网络来支持给定的通信模式。这两个领域的问题是组合优化的核心问题，有许多应用. 本文研究的问题是NP难问题，得到多项式时间近似算法的方法以及基于松弛的线性规划的完整性间隙的界。议程的核心问题是无向图中的不相交路径问题、批量购买网络设计和定向越野。 除了改进这些问题的算法外，还有望发现新的广泛适用的算法技术。有几个应用可以直接受益，包括超大规模集成电路设计，网络中的带宽和资源分配，光网络设计和车辆布线。该项目将支持和培训博士生，并通过新课程和课堂讲稿帮助传播先进的算法思想。

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.