Tom Leighton
Satish Rao
- AGRAWAL, A., KLEIN, P.N., AND RAVI, R. 1993. Cutting down on fill using nested dissection: Provably good elimination orderings. In Graph Theory and Sparse Matrix Computation, A. George, J. Gilbert, and J. W. H. Liu, eds. IMA Volumes in Mathematics and Its Applications, Springer- Verlag, New York, pp. 31-55.Google Scholar
- AGORA, S., KARGER, D., AND KARPINSKI, M. 1995. Polynomial time approximation schemes for dense instances of NP-hard problems. In Proceedings of the 27th Annual ACM Symposium on Theory of Computing (Las Vegas, Nev., May 29-June 1). ACM, New York, pp. 284-293. Google Scholar
- AUMANN, Y. AND RABANI, Y. 1995. Improved bounds for all-optical routing. In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, Calif., Jan. 22-24), ACM, New York, pp. 567-576. Google Scholar
- AUMANN, Y. AND RABANI, Y. 1998. An O(log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput. 27, 1, 291-301. Google Scholar
- AWERBUCH, B., BERGER, B., COWEN, L., AND PELEG, D. 1999. Near-linear cost constructions of neighborhood covers in sequential and distributed environments. SIAM J. Comput. 28, 1,263-277. Google Scholar
- AWERBUCH, B. AND LEIGHTON, T. 1994. Improved approximation algorithms for the multicommodity flow problem and local competitive routing in dynamic networks. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing (Montreal, Que., Canada, May 23-25). ACM, New York, pp. 487-495. Google Scholar
- AWERBUCH, B. AND PELEG, D. 1990. Sparse partitions. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 503-513.Google Scholar
- BENCZUR, A. AND KARGER, D. 1996. Approximate s-t min-cuts in O(n2) time. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing (Philadelphia, Pa., May 22-24). ACM, New York, pp. 47-55. Google Scholar
- BHATT, S. N. AND LEIGHTON, F.T. 1984. A framework for solving VLSI graph layout problems. J. Comput. Syst. Sci. 28, 2, 300-343.Google Scholar
- BODLAENDER, H., HAFSTEINSSON, H., GmBEaT, J. R., AND KLOKS, T. 1995. Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. J. Algorithms 18, 238-255. Google Scholar
- BOURGAIN, J.1985. On Lipschitz embedding of finite metric spaces in Hilbert space. Is. J. Math. 52, 46 -52.Google Scholar
- BaODEa, A. Z., FamzE, A. M., AND UPFAL, E. 1992. Existence and construction of edge disjoint paths on expander graphs. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing (Victoria, B.C., Canada, May 4-6). ACM, New York, pp. 140-149. Google Scholar
- BRODER, A.Z., FRIEZE, A.M., AND UPFAL, E. 1997. Static and dynamic path selection on expander graphs: A random walk approach. In Proceedings of the 29th Annual ACM Symposium on the Theory of Computing (El Paso, Tex., May 4-6), ACM, New York, pp. 531-539. Google Scholar
- CHUNG, F. K., COFFMAN, E. G., REIMAN, M. I., AND SIMON, B.E. 1987. The forwarding index of communication networks. IEEE Trans. Inf. Theory 33, 224-232. Google Scholar
- CHVATAL, V. 1983. Linear Programming. Freeman, San Francisco, Calif.Google Scholar
- COHEN, E. 1993. Fast algorithms for constructing t-spanners and paths with stretch t. In Proceedings of the 34th Annual Symposium on Foundations of Computer Science (Nov.), IEEE Computer Society Press, Los Alamitos, Calif., pp. 648-658.Google Scholar
- DIACONIS, P. AND STROOCK, D. 1991. Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Prob. 1, 36-61.Google Scholar
- DOLEV, D., LEIGHTON, F. T., AND TRICKEY, H. 1983. Planar embeddings of planar graphs. Tech. rep. HIT, Cambridge, Mass.Google Scholar
- ELLIS, J.A., SUDBOROUGH, I.H., AND TURNER, J.S. 1994. The vertex separation and search number of a graph. Inf. Comput. 113, 50-79. Google Scholar
- EVEN, G., NAOR, J., RAG, S., AND SCHIEBER, B. 1995. Divide-and-conquer approximation algorithms via spreading metrics. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science (Oct.), IEEE Computer Society Press, Los Alamitos, Calif., pp. 62-71. Google Scholar
- EVEN, G., NAOR, J., RAG, S., AND SCHIEBER, B. 1997. Fast approximate graph partitioning algorithms. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, pp. 639-648. Google Scholar
- EVEN, G., NAOR, J., SCHIEBER, B., AND SUDAN, M. 1998. Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica 20, 2, 151-174.Google Scholar
- FORD, L.R. AND FULKERSON, D.R. 1956. Sur le probldme des courbes gauches en topologie. Canad. J. Math 8, 399-404.Google Scholar
- FRANK, A. 1990. Packing paths, circuits and cuts--A survey. In Paths, Flows, and VLSI-Layout, B. Korte, L. Lovfisz, H.J. Pr6mel, and A. Schrijver, eds. Springer-Verlag, Berlin, Germany, pp. 47-100.Google Scholar
- GAREY, M. R. AND JOHNSON, D.S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, Calif. Google Scholar
- GARG, N., VAZARANI, V., AND YANNAKAKIS, M. 1996. Approximate max-flow min-(multi)cut theorems and their applications. SIAM J. Comput. 25, 235-251. Google Scholar
- HANSEN, M. 1989. Approximation algorithms for geometric embeddings in the plane and applications to parallel processing problems. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science (Oct.). IEEE Computer Science Society Press, Los Alamitos, Calif., pp. 604-609.Google Scholar
- HEYDEMANN, M.C., MEYER, J. C., AND SOTTEAU, D. 1989. On forwarding indices of networks. Discrete Applied Mathematics 23, 103-123. Google Scholar
- HEYDEMANN, M.C., MEYER, J. C., AND SOTTEAU, D. 1992. Forwarding indices of k-connected graphs. Disc. Appl. Math. 37/38, 287-296. Google Scholar
- HEYDEMANN, M.C., MEYER, J.C., AND SOTTEAU, D. 1994. Forwarding indices of consistent routings and their complexity. Networks 24, 75-82.Google Scholar
- Hu, T.C. 1963. Multicommodity network flows. Oper. Res. 11, 3, 344-360.Google Scholar
- IRI, M. 1967. On an extension of the maximum-flow minimum cut theorem to multicommodity flows. J. Oper. Res. Soc. Japan 5, 4 (Dec.), 697-703.Google Scholar
- KAMATH, A. AND PALMON, 0. 1995. Improved interior point algorithms for exact and approximate solutions of multicommodity flow problems. In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, Calif., Jan. 22-24). ACM, New York, pp. 502-511. Google Scholar
- KIROUSIS, L. M. AND PAPADIMITRIOU, C.H. 1986. Searching and pebbling. Theoret. Comput. Sci. 4 7, 205-216. Google Scholar
- KLEIN, P., AGRAWAL, A., RAO, S., AND RAVI, R. 1989. Approximation through multicommodity flow. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science (Oct.). IEEE Computer Society Press, Los Alamitos, Calif., pp. 726-737.Google Scholar
- KLEIN, P., PLOTKIN, S., RAO, S., AND TARDOS, E. 1997. Bounds on the max-flow min-cut ratio for directed multicommodity flows. J. Algorithms 22, 241-269. Google Scholar
- KLEIN, P., PLOTKIN, S., STEIN, C., AND TARDOS, E. 1994. Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts. SIAM J. Comput. 23, 466-487. Google Scholar
- KLEIN, P., RAO, S., AGRAWAL, A., AND RAVI, R. 1995. Approximation through multicommodity flow. Combinatorica 15, 187-202.Google Scholar
- KLEIN, P., PLOTKIN, S., AND RAO, S. 1993. Excluded minors, network decomposition, and multicommodity flow. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing (San Diego, Calif., May 16-18). ACM, New York, pp. 682-690. Google Scholar
- KLEIN, P. N., BORGER, J. M., AND KANG, S. 1991. Approximating concurrent flow with uniform demands and capacities: An implementation. In Proceedings of DIMACS Implementation Challenge Workshop: Network Flows and Matching (Oct.). AMS, Providence, R.I., pp. 371-386.Google Scholar
- LANG, K. AND RAO, S. 1993. Finding near-optimal cuts: An empirical evaluation. In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, pp. 212-221. Google Scholar
- LEIGHTON, F.T. 1983. Complexity Issues in VLSI: Optimal Layouts for the Shuffle-Exchange Graph and Other Networks. MIT Press, Cambridge, Mass. Google Scholar
- LEIGHTON, F.T., MAGGS, B., AND RAO, S. 1994. Packet routing and job-shop scheduling in o(congestion + dilation) steps. Combinatorica 14, 2, 167-180.Google Scholar
- LEIGHTON, F. T. AND RAO, S. 1996. Circuit switching: A multicommodity flow based approach. In Proceedings of the 1st Workshop on Randomized Parallel Computing (Apr.).Google Scholar
- LEIGHTON, F. T., RAO, S. B., AND SRINIVASAN, A. 1998. Multi-commodity flow and circuit switching. In Proceedings of the 31st Hawaii International Conference on System Sciences, vol. 7. IEEE Computer Society Press, Los Alamitos, Calif., pp. 466-474. Google Scholar
- LEIGHTON, F.T. AND RAO, S. 1988. An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 256-269.Google Scholar
- LEIGHTON, F. T., MAKEDON, F., PLOTKIN, S., STEIN, C., TARDOS, E., AND TRAGOUDAS, S. 1992. Fast approximation algorithms for multicommodity flow problems. J. Comput. Syst. Sci. 50, 228-243. Google Scholar
- LEIGHTON, F.T., MAKEDON, F., AND TRAGOUDAS, S. 1990. Approximation algorithms for VLSI partition problems. In Proceedings of the IEEE International Symposium on Circuits and Systems. IEEE Computer Society Press, Los Alamitos, Calif.Google Scholar
- LEIGHTON, f. AND MAGGS, B. 1995. Fast algorithms for finding O(congestion + dilation) packet routing schedules. In Proceedings of the 28th Hawaii International Conference on System Sciences (HICSS), vol. 2. IEEE Computer Society Press, Los Alamitos, Calif., pp. 555-563. Google Scholar
- LEIGHTON, f., MAGGS, B., AND RICHA, A. 1995. Fast algorithms for finding O(congestion + dilation) packet routing schedules. Tech. Rep. School of Computer Science, Carnegie Mellon University, Pittsburgh, Pa.Google Scholar
- LEISERSON, C.E. 1980. Area-efficient layouts (for VLSI). In Proceedings of the 21st Annual Symposium on Foundations of Computer Science (Oct.). IEEE Computer Science Press, Los Alimatos, Calif., pp. 270-281.Google Scholar
- LEONG, f., SHOR, P., AND STEIN, C. 1991. Implementation of a combinatorial multicommodity flow algorithm. In DIMACS Series in Discrete Mathematics and Theoretical Computer Science: Volume 12, Network Flows and Matching, D. S. Johnson and C. C. McGeoch, eds. (Oct.). AMS, Providence R.I., pp. 387-406.Google Scholar
- LINIAL, N., LONDON, E., AND RABINOVICH, f. 1995. The geometry of graphs and some of its algorithmic applications. Combinatorica 15, 215-245.Google Scholar
- LIPTON, J. AND TARJAN, R.E. 1979. A separator theorem for planar graphs. SIAM J. Appl. Math. 36, 2 (Apr.), 177-189.Google Scholar
- LOMONOSOV, M.V. 1985. Combinatorial approaches to multiflow problems. Disc. Appl. Math. 11, 1-94.Google Scholar
- Lov#.sz, L. 1991. Random walk on graphs: A survey. Tech. Rep. Dept. Computer Science, Yale Univ., New Haven, Conn.Google Scholar
- MARGULIS, G.A. 1973. Explicit constructions of concentrators. Prob. Inf. Trans. 9, 325-332.Google Scholar
- MATULA, D. W. AND SHAHROKHI, F. 1986. The maximum concurrent flow problem and sparsest cuts. Tech. Rep. Southern Methodist Univ., Dallas, Tex.Google Scholar
- OKAMURA, H. AND SEYMOUR, P.D. 1981. Multicommodity flows in planar graphs. J. Combin. Theory, Ser. B 31, 75-81.Google Scholar
- PAPERNOV, B.A. 1990. Feasibility of multicommodity flows (in Russian). In Studies in Discrete Optimization, A. A. Friedman, ed. New York, pp. 17-34.Google Scholar
- PARK, J. AND PHILLIPS, C. 1993. Finding minimum quotient cuts in planar graphs. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing (San Diego, Calif., May 16-18). ACM, New York, pp. 766-775. Google Scholar
- PELEG, D. AND UPFAL, E. 1989. The token distribution problem. SIAM J. Comput. 18, 2 (Apr.), 229-243. Google Scholar
- PLOTKIN, S. AND TARDOS, E. 1993. Improved bounds on the max-flow min-cut ratio for multicommodity flows. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing (San Diego, Calif., May 16-18). ACM, New York, pp. 691-697. Google Scholar
- RAGHAVAN, P. 1988. Probabilistic construction of deterministic algorithms: Approximate packing integer programs. J. Comput. Syst. Sci. 37, 4 (Oct.), 130-143. Google Scholar
- RAGHAVAN, P. AND UPFAL, E. 1994. Efficient routing all-optical networks. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing (Montreal, Que., Canada, May 23-25). ACM, New York, pp. 134-143. Google Scholar
- RAO, S. 1992. Faster algorithms for finding small edge cuts in planar graphs. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing (Victoria, B.C., Canada, May 4-6). ACM, New York, pp. 229-240. Google Scholar
- RAVI, R., AGRAWAL, A., AND KLEIN, P.N. 1991. Ordering problems approximated: Single-processor scheduling and interval graph completion. In Proceedings, 18th International Conference on Automata, Languages, and Programming. Lecture Notes in Computer Science, vol. 510. Springer- Verlag, New York, pp. 751-762. Google Scholar
- SCHRIJVER, A. 1990. Homotopic routing methods. In Paths, Flows, and VLSI-Layout, B. Korte, L. Lovfisz, H. J. Pr6mel, and A. Schrijver, eds. Springer-Verlag, Berlin, Germany, pp. 329-371.Google Scholar
- SEYMOUR, P.D. 1995. Packing directed circuits fractionally. Combinatorica 15, 281-288.Google Scholar
- SHAHROKHI, F. AND MATULA, D.W. 1990. The maximum concurrent flow problem. J. ACM 37, 318-334. Google Scholar
- SHMOYS, D.B. 1996. Cut problems and their application to divide-and-conquer. In Approximation Algorithms, D. S. Hochbaum, ed. PWS Publishers, Boston, Mass., pp. 192-235. Google Scholar
- SINCLAIR, A. 1991. Improved bounds for mixing rates of Markov chains and multicommodity flow. Tech. Rep. Laboratory for Foundations of Computer Science, Department of Computer Science, The University of Edinburgh, Edinburgh, Scotland.Google Scholar
- SINCLAIR, A. 1993. Algorithms for Random Generating and Counting. Birkhfiuser, Boston, Mass. Google Scholar
- SINCLAIR, A. J. AND JERRUM, M.R. 1989. Approximate counting, uniform generation and rapidly mixing Markov chains. Inf. Comput. 82, 93-133. Google Scholar
- TARJAN, R.E. 1983. Data Structures and Network Algorithms. SIAM, Philadelphia, Pa. Google Scholar
- TRAGOUDAS, S. 1990. VLSI partitioning approximation algorithms based on multicommodity flows and other techniques. Ph.D. dissertation. Dept. Comput. Sci., Univ. Texas, Dallas, Dallas, Tex. Google Scholar
- VAIDYA, P.M. 1989. Speeding up linear programming using fast matrix multiplication. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, pp. 332-337.Google Scholar
- VALIANT, k.1981. Universality considerations in VLSI circuits. IEEE Trans. Comput. C-30, 2, 135-140.Google Scholar
- YEH, C. W., CHENG, C. K., AND LIN, f.f. 1992. A probabilistic multicommodity-flow solution to circuit clustering problems. In Proceedings of the IEEE International Conference on Computer-Aided Design. IEEE Computer Society Press, Los Alamitos, Calif. pp. 428-431. Google Scholar
Index Terms
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
Recommendations
A New Min-Cut Max-Flow Ratio for Multicommodity Flows
In this paper we present a new bound on the min-cut max-flow ratio for multicommodity flow problems with specified demands. For multicommodity flows, this is a generalization of the well-known relationship between the capacity of a minimum cut and the ...
Approximation Algorithms for Requirement Cut on Graphs
In this paper, we unify several graph partitioning problems including multicut, multiway cut, and k-cut, into a single problem. The input to the requirement cut problem is an undirected edge-weighted graph G=(V,E), and g groups of vertices X1,ź,Xg⊆V, ...
A Polylogarithmic Approximation of the Minimum Bisection
A bisection of a graph with n vertices is a partition of its vertices into two sets, each of size n/2. The bisection cost is the number of edges connecting the two sets. It is known that finding a bisection of minimum cost is NP-hard. We present an ...
Reviews
Patrick J. Ryan
The authors study the relationship between the max-flow and the min-cut for multicommodity flow problems. The min-cut is an upper bound for the max-flow, and the fundamental theorem of Ford and Fulkerson shows that for a 1-commodity problem, the two are equal. It has also been shown that they are equal for 2-commodity problems. However, they are not equal in general. The paper's main result is that there is a constant C such that, for any uniform multicommodity flow problem, the ratio of the max-flow to the min-cut is at least C/ log n , where n is the number of nodes. The authors also show that there exists a family of problems (one for each n ) for which the ratio is in O 1/ log n . In this sense, the main result is the best possible. (Uniformity means that there is a commodity for every pair of nodes and all commodities have the same demand.) They apply their results to the design of polynomial-time approximation algorithms for well-known NP-hard problems, such as graph partitioning. This is a journal version of a seminal work made known informally and in abstract form over ten years ago. Its influence on an entire area of research—approximation algorithms for graph partitioning and related problems—has been discussed by Shmoys [1]. The paper is long (over 40 pages), with a bibliography of more than 60 references. Some 30 individuals are acknowledged, and the referees are credited with having made hundreds of suggestions. The style of the presentation reflects this.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments