Content area
Abstract
The construction of disjoint paths in a network is a basic issue in combinatorial optimization: given a network, and specified pairs of nodes in it, we are interested in finding disjoint paths between as many of these pairs as possible. This leads to a variety of classical NP-complete problems for which very little is known from the point of view of approximation algorithms. It has recently been brought into focus in work on problems such as VLSI layout and routing in high-speed networks; in these settings, the current lack of understanding of the disjoint paths problem is often an obstacle to the design of practical heuristics.
We develop a number of general techniques for designing approximation algorithms for disjoint paths problems. Our approach leads to the first constant-factor approximation algorithm for the maximum disjoint paths problem on the two-dimensional mesh, as well as on a class of planar networks generalizing the mesh. We obtain a number of related algorithms by this approach, including a routing algorithm for the mesh that is optimal in the on-line model considered in much of the recent work on this problem; here connection requests arrive over time and must be processed immediately. Underlying a number of our results is a new approximation algorithm for a basic, NP-hard variant of the maximum flow problem. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.)
