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.