P. Klein
C. Stein
É. Tardos
- 1.R. Dial. Algorithm 360: Shortest path forest with topological ordering. Communications of the ACM, 12:632- 633, 1969. Google Scholar
Digital Library
- 2.M.L. Fredman and R.E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34:596-615, 1987. Google ScholarDigital Library
- 3.A. V. Goldberg and R. E. Tarjan. finding minimumcost circulations by successive approximation. Technical Report MIT/LCS/TM-333, Laboratory for Computer Science, M.I.T., 1987. (Math. of Oper. Res., to appear).Google Scholar
- 4.S. Kapoor and P. M. Vaidya. Fast algorithms for convex quadratic programming and multicommodity flows. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing, pages 147-159, 1986. Google ScholarDigital Library
- 5.P. Klein and C. Stein. Leighton-Rao might be practical: a faster approximation algorithm for uniform concurrent flow. Unpublished manuscript, November 1989.Google Scholar
- 6.F. T. Leighton, November 1989. Private communication.Google Scholar
- 7.T. Leighton and S. Rao. An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pages 422-431. IEEE, October 1988.Google ScholarDigital Library
- 8.P. Raghavan. Probabilistic construction of deterministic algorithms: approximating packing integer programs. In Proceedings of the 27th Annual Symposium on Foundations of Computer Science, pages 10- 18, 1986.Google ScholarDigital Library
- 9.P. Raghavan and C. D. Thompson. Provably good routing in graphs: regular arrays. In Proceedings of the 17th Annual ACM Symposium on Theory of Computing, pages 79-87, 1985. Google ScholarDigital Library
- 10.F. Shahrokhi and D. W. Matula. The maximum concurrent flow problem. Technical Reprot CSR-283, New Mexico Tech., 1988.Google Scholar
- 11.D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees. Journal of Computer and System Sciences, 26:362-391, 1983. Google ScholarDigital Library
- 12.E. Tardos. Improved approximation algorithm for concurrent multi-commodity flows. Technical Report 872, School of Operations Research and Industrial Engineering, Cornell University, October 1989.Google Scholar
- 13.P. M. Valdya. Speeding up finear programming using fast matrix multiplication. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science, pages 332-337, 1989.Google Scholar
Index Terms
- Leighton-Rao might be practical: faster approximation algorithms for concurrent flow with uniform capacities
Recommendations
Zero/Positive Capacities of Two-Dimensional Runlength-Constrained Arrays
A binary sequence satisfies a one-dimensional $(d_1, k_1, d_2, k_2)$ runlength constraint if every run of zeros has length at least $d_1$ and at most $k_1$ and every run of ones has length at least $d_2$ and at most $k_2$ . A two-dimensional binary ...
Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems
In this paper we study the (in)approximability of two distance-based relaxed variants of the maximum clique problem (Max Clique), named Max d-Clique and Max d-Club: A d-clique in a graph $$G = (V, E)$$G=(V,E) is a subset $$S\subseteq V$$S⊆V of vertices ...
Comments