Design of Efficient Algorithms for Multicommodity Flow and Related Combinatorial Optimization Problems

该项目研究组合优化，重点是与商品流动和最小比切割有关的问题。对这些问题的组合结构的深入理解将导致各种应用的改进算法，包括图平分，小面积VLSI布局，调度和路由。目前已知的用于寻找多商品流精确解的算法都非常缓慢。这些算法基于一般线性规划（LP）技术，没有利用问题的潜在组合结构。应用一般LP技术来解决这类问题会导致更慢的算法。该项目的主要目标是寻找解决多种商品流动和相关问题的替代方法。目标是提高顺序和并行复杂度。在许多应用中，求解多商品流只是近似求解np完全问题的第一步；在大多数这种情况下，不需要有多商品流动问题的精确解决方案。该项目的重点之一是开发有效的近似算法的设计。多商品流方法的另一个自然应用是在分布式通信网络中的路由领域。例如，与管理可用带宽有关的问题可以表述为多种商品流量的变体，其中信息速率对应于流量，每个链接的带宽对应于其容量。通信网络的分布式、实时性提出了一些具有挑战性的障碍，这些障碍在离线、顺序设置中不存在。其中一个问题是，并非所有的信息都是事先已知的，这意味着算法必须在线工作。其次，通常不存在拥有关于网络的完整信息并做出所有决策的“管理”节点。因此，算法应该只处理部分信息。

The project studies combinatorial optimization, with emphasis on problems related to commodity flow and minimum-ratio cuts. Deeper understanding of the combinatorial structure of these problems will result in improved algorithms for a variety of applications, including graph bisection, small area VLSI layout, scheduling, and routing. All of the currently known algorithms for finding exact solutions to multicommodity flow are very slow. These algorithms are based on general linear programming (LP) techniques and do not take advantage of the underlying combinatorial structure of the problem. Applying general LP techniques to solving such problems leads to even slower algorithms. The main goal of this project is to find alternative approaches to solving multicommodity flow and related problems. The goal is to improve both sequential and parallel complexity. In many applications, solving a multicommodity flow is only a first step in approximately solving an NP-complete problem; in the majority of such cases there is no need to have an exact solution of the multicommodity flow problem. One of the focuses of the project is to develop the design of efficient approximation algorithms. Another natural application of the multicommodity flow methods is in the area of routing in distributed communication networks. For example, problems related to managing available bandwidth can be stated as variants of multicommodity flow, where the information rate corresponds to flow and the bandwidth of every link corresponds to its capacity. The distributed, real-time nature of communication networks presents several challenging obstacles that do not exist in an off-line, sequential setting. Among them is the fact that not all the information is known in advance, which means that the algorithms have to work on-line. Second, there is usually no `manager` node that has a complete information about the network and that makes all the decisions. Therefore, the algorithms should work with partial information.