Approximation Algorithms for Routing and Network Design

路由和网络设计的近似算法

• 批准号: 0728782
• 负责人: Chandra Chekuri
• 金额: $ 29.2万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-01 至 2011-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0728782&HistoricalAwards=false
• 关键词: Approximation; Algorithms; Routing; 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.

该项目的目的是获取新的算法和见解，这些算法和洞察力在图形和网络中的基本问题充满了重点，并以重点介绍和网络设计。 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. 同样，网络设计中的一个原型问题是建立一个最低成本网络，以支持给定的通信模式。这两个领域的问题是与许多应用的组合极次临时化的核心。 它们在算法和结构图理论的开发中也起着至关重要的作用。该项目中考虑的问题是NP-HARD和获得多项式时间近似算法的方法，以及基于线性编程的整数差距的差距。议程中心的问题是无方向图，购买网络设计，Andorienteering中的脱节路径问题。 除了改进这些雄性问题的算法外，还可以发现新的广泛适用算法技术。有几种应用程序会受益于网络中的VLSI设计，带宽和ResourceCealLocation，光网络设计和VehiclerOuting。该项目将支持和培训博士生，并通过新的课程和注释来帮助传播先进的算法思想。