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

多商品流高效算法设计及相关组合优化问题

• 批准号: 9304971
• 负责人: Serge Plotkin
• 金额: $ 20.52万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1994
• 资助国家: 美国
• 起止时间: 1994-05-01 至 1998-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9304971&HistoricalAwards=false
• 关键词: Design; Efficient; Algorithms; Multicommodity; Flow

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.

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