Abstract/Details

Approximation algorithms for disjoint paths problems

Kleinberg, Jon Michael.   Massachusetts Institute of Technology ProQuest Dissertations Publishing,  1996. 0597431.

Abstract (summary)

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.)

Indexing (details)


Subject
Computer science
Classification
0984: Computer science
Identifier / keyword
Applied sciences; combinatorial optimization
Title
Approximation algorithms for disjoint paths problems
Author
Kleinberg, Jon Michael
Number of pages
1
Degree date
1996
School code
0753
Source
DAI-B 57/08, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
Advisor
Goemans, Michel X.
University/institution
Massachusetts Institute of Technology
University location
United States -- Massachusetts
Degree
Ph.D.
Source type
Dissertation or Thesis
Language
English
Document type
Dissertation/Thesis
Dissertation/thesis number
0597431
ProQuest document ID
304318648
Copyright
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
https://www.proquest.com/docview/304318648