Approximation Algorithms for Routing and Network Design

这个项目的目标是为图和网络中的一些基本问题获得新的算法和见解，重点是布线和网络设计。路由中的一个典型问题是寻找连接一组给定源-目的节点对的路径，同时遵守底层网络的链路和节点容量限制。同样，网络设计中的一个典型问题是建立一个支持给定通信模式的最小成本网络。这两个领域的问题是组合优化的核心问题，有着广泛的应用。它们在算法和结构图理论的发展中也起着至关重要的作用。本项目所考虑的问题是NP-Hard问题，是获得多项式时间近似算法的方法，以及基于松弛的线性规划的完整性缺口的界。议程的核心问题是无向图中的不相交路径问题、批量购买网络设计和定向运动。除了针对这些问题和相关问题的改进算法外，还有望发现新的广泛适用的算法技术。有几个应用可以直接受益，包括VLSI设计、网络中的带宽和资源分配、光网络设计和车辆路线选择。该项目将支持和培训博士生，并通过新的课程和课堂讲稿帮助传播先进的算法思想。

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.