DocumentCode :
3174718
Title :
An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms
Author :
Leighton, Tom ; Rao, Satish
Author_Institution :
MIT, Cambridge, MA, USA
fYear :
1988
fDate :
24-26 Oct 1988
Firstpage :
422
Lastpage :
431
Abstract :
A multicommodity flow problem is considered where for each pair of vertices (u, v) it is required to send f half-units of commodity (u, v) from u to v and f half-units of commodity (v, u) from v to u without violating capacity constraints. The main result is an algorithm for performing the task provided that the capacity of each cut exceeds the demand across the cut by a Θ(log n) factor. The condition on cuts is required in the worst case, and is trivially within a Θ(log n) factor of optimal for any flow problem. The result can be used to construct the first polylog-times optimal approximation algorithms for a wide variety of problems, including minimum quotient separators, 1/3-2/3 separators, bifurcators, crossing number, and VLSI layout area. It can also be used to route packets efficiently in arbitrary distributed networks
Keywords :
graph theory; 1/3-2/3 separators; VLSI layout area; approximation algorithms; bifurcators; crossing number; distributed networks; max-flow min-cut theorem; minimum quotient separators; multicommodity flow problems; optimal approximation; Application software; Approximation algorithms; Bifurcation; Computer science; Constraint theory; Contracts; Laboratories; Linear programming; Mathematics; Particle separators;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 1988., 29th Annual Symposium on
Conference_Location :
White Plains, NY
Print_ISBN :
0-8186-0877-3
Type :
conf
DOI :
10.1109/SFCS.1988.21958
Filename :
21958
Link To Document :
بازگشت