An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms
- 1 January 1988
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 422-431
- https://doi.org/10.1109/sfcs.1988.21958
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 Theta (log n) factor. The condition on cuts is required in the worst case, and is trivially within a Theta (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
This publication has 10 references indexed in Scilit:
- Universal packet routing algorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Eigenvalues and graph bisection: An average-case analysisPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- Finding near optimal separators in planar graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- Graph bisection algorithms with good average case behaviorCombinatorica, 1987
- The token distribution problemPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- Probabilistic construction of deterministic algorithms: Approximating packing integer programsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- Tight Bounds on the Complexity of Parallel SortingIEEE Transactions on Computers, 1985
- A framework for solving VLSI graph layout problemsJournal of Computer and System Sciences, 1984
- A Linear-Time Heuristic for Improving Network PartitionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- An Efficient Heuristic Procedure for Partitioning GraphsBell System Technical Journal, 1970