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 困难的。该项目旨在加深对这些基本优化问题的多项式时间逼近性的理解，并对多种商品流、切割和整体路线之间的关系获得新的见解。这项研究将重点关注新的算法技术以及新的硬度和完整性间隙结构，以深入了解这些问题的组合结构。尽管这些问题本质上是基础性的，但它们与网络设计和路由以及资源分配中的应用直接相关。这项研究获得的结果将被纳入组合优化的高级课程中。该项目还将帮助支持和培训研究生以及本科生的研究项目。