Cuts, Flows, and Network Routing

这个计画的目标是研究基本网路最佳化问题的计算易处理性，例如不相交路径、拥塞最小化和多重切割。例如，给定一个网络和一组源-目的地对，如何在不引起拥塞的情况下将每个源路由到其目的地？哪一组最小的网络链路的故障会断开每个源与其目的地之间的连接？这些优化问题通过网络中的割和流的双重概念彼此密切相关。两者合计，它们是最广泛研究的组合优化问题之一，并且是计算机科学中许多应用所固有的。毫不奇怪，这些问题的研究与算法设计、逼近难度和图论的重大发展有关。上述网络优化问题即使在简单的设置下也是NP难的。该项目旨在促进对这些基本优化问题的多项式时间近似性的理解，并对多商品流，切割和积分路由之间的关系获得新的见解。这项研究将集中在新的算法技术，以及新的硬度和完整性差距的建设，使这些问题的组合结构的见解。虽然这些问题本质上是基础性的，但它们直接关系到网络设计和路由以及资源分配中的应用。从这项研究中获得的结果将被整合在一个先进的过程中组合优化。该项目还将帮助支持和培训一名研究生，以及本科生的研究项目。

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.