Cuts, Flows, and Network Routing

剪切、流和网络路由

• 批准号: 0635084
• 负责人: Sanjeev Khanna
• 金额: --
• 依托单位: University of Pennsylvania
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-09-15 至 2011-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0635084&HistoricalAwards=false
• 关键词: Cuts; Flows; Network; Routing

The goal of this project is to study the computational tractability of fundamental network optimization problems such as disjoint paths, congestion minimization, and multicut. For instance, given a network, and a collection of source-destination pairs, how does one route each source to its destination without causing congestion?What is a smallest set of network links whose failure disconnects each source from its destination? These optimization problems are intimately related to each other via the dual notions of cuts and flows in a network. Taken together, they are among the most widely studied combinatorial optimization problems, and are intrinsic to many applications in computer science. It is no surprise that the study of these problems is connected to major developments in algorithms design, hardness of approximation, and graph theory.The network optimization problems above are NP-hard even in simple settings. This project aims to advance understanding of the polynomial-time approximability of these fundamental optimization problems as well as gain new insights into relationships among multicommodity flows, cuts, and integral routings. This research will focus on new algorithmic techniques as well as new hardness and integrality gap constructions that give insights into the combinatorial structure of these problems. Although these problems are foundational in nature, they are directly related to applications in network design and routing, and resource allocation. Results obtained from this research will be integrated in an advanced course on combinatorial optimization. The project will also help support and train a graduate student, as well as research projects for undergraduates.

该项目的目的是研究基本网络优化问题的计算障碍，例如脱节路径，交通拥堵最小化和多速度。例如，给定一个网络和一系列源用途对，一个人如何将每个源路由到其目的地而不会引起拥塞？什么是最小的网络链接，其故障使每个源从其目的地断开连接的最小网络链接？这些优化问题是通过网络中的剪切和流动的双重概念彼此密切相关的。综上所述，它们是研究最广泛的组合优化问题之一，并且是计算机科学中许多应用的内在性。毫不奇怪的是，这些问题的研究与算法设计，近似硬度和图理论的主要发展有关。上面的网络优化问题即使在简单的设置中也是NP-HARD。该项目旨在提高对这些基本优化问题的多项式时间近似性的了解，并获得对多商品流，削减和整体路由之间关系的新见解。这项研究将重点介绍新的算法技术以及新的硬度和完整性差距结构，从而洞悉这些问题的组合结构。尽管这些问题本质上是基本的，但它们与网络设计和路由以及资源分配中的应用直接相关。从这项研究中获得的结果将集成到组合优化的高级课程中。该项目还将帮助支持和培训研究生，以及针对本科生的研究项目。