Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms

Full text

Pdf (318 KB)

Source

Journal of the ACM (JACM) archive
Volume 46 , Issue 6 (November 1999) table of contents

Pages: 787 - 832

Year of Publication: 1999

ISSN:0004-5411

Authors

Tom Leighton	Massachusetts Institute of Technology, Cambridge
Satish Rao	NEC Research Institute, Princeton, NJ

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 59, Downloads (12 Months): 746, Citation Count: 85

Additional Information:

references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/331524.331526 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	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.
	2	Sanjeev Arora , David Karger , Marek Karpinski, Polynomial time approximation schemes for dense instances of NP-hard problems, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.284-293, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225140]
	3	Yonatan Aumann , Yuval Rabani, Improved bounds for all optical routing, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.567-576, January 22-24, 1995, San Francisco, California, United States
	4	Yonatan Aumann , Yuval Rabani, An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm, SIAM Journal on Computing, v.27 n.1, p.291-301, Feb. 1998 [doi>10.1137/S0097539794285983]
	5	Baruch Awerbuch , Bonnie Berger , Lenore Cowen , David Peleg, Near-Linear Time Construction of Sparse Neighborhood Covers, SIAM Journal on Computing, v.28 n.1, p.263-277, Feb. 1999 [doi>10.1137/S0097539794271898]
	6	Baruch Awerbuch , Tom Leighton, Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.487-496, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195238]
	7	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.
	8	András A. Benczúr , David R. Karger, Approximating s-t minimum cuts in Õ(n²) time, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.47-55, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237827]
	9	BHATT, S. N. AND LEIGHTON, F.T. 1984. A framework for solving VLSI graph layout problems. J. Comput. Syst. Sci. 28, 2, 300-343.
	10	Hans L. Bodlaender , John R. Gilbert , Hjálmtýr Hafsteinsson , Ton Kloks, Approximating treewidth, pathwidth, frontsize, and shortest elimination tree, Journal of Algorithms, v.18 n.2, p.238-255, March 1995 [doi>10.1006/jagm.1995.1009]
	11	BOURGAIN, J.1985. On Lipschitz embedding of finite metric spaces in Hilbert space. Is. J. Math. 52, 46 -52.
	12	Andrei Z. Broder , Alan M. Frieze , Eli Upfal, Existence and construction of edge disjoint paths on expander graphs, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.140-149, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129727]
	13	Andrei Z. Broder , Alan M. Frieze , Eli Upfal, Static and dynamic path selection on expander graphs (preliminary version): a random walk approach, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.531-539, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258646]
	14	F. R. K. Chung , E.G. Coffman, Jr. , M.I. Reiman , B. Simon, The forwarding index of communication networks, IEEE Transactions on Information Theory, v.33 n.2, p.224-232, March 1987 [doi>10.1109/TIT.1987.1057290]
	15	CHVATAL, V. 1983. Linear Programming. Freeman, San Francisco, Calif.
	16	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.
	17	DIACONIS, P. AND STROOCK, D. 1991. Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Prob. 1, 36-61.
	18	DOLEV, D., LEIGHTON, F. T., AND TRICKEY, H. 1983. Planar embeddings of planar graphs. Tech. rep. HIT, Cambridge, Mass.
	19	J. A. Ellis , I. H. Sudborough , J. S. Turner, The vertex separation and search number of a graph, Information and Computation, v.113 n.1, p.50-79, Aug. 15, 1994 [doi>10.1006/inco.1994.1064]
	20	G. Even , J. Naor , S. Rao , B. Schieber, Divide-and-conquer approximation algorithms via spreading metrics, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.62, October 23-25, 1995
	21	Guy Even , Joseph (Seffi) Naor , Satish Rao , Baruch Schieber, Fast approximate graph partitioning algorithms, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.639-648, January 05-07, 1997, New Orleans, Louisiana, United States
	22	EVEN, G., NAOR, J., SCHIEBER, B., AND SUDAN, M. 1998. Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica 20, 2, 151-174.
	23	FORD, L.R. AND FULKERSON, D.R. 1956. Sur le probldme des courbes gauches en topologie. Canad. J. Math 8, 399-404.
	24	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.
	25	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	26	Naveen Garg , Vijay V. Vazirani , Mihalis Yannakakis, Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications, SIAM Journal on Computing, v.25 n.2, p.235-251, February 1996 [doi>10.1137/S0097539793243016]
	27	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.
	28	M. C. Heydemann , J.c. Meyer , D. Sotteau, On forwarding indices of networks, Discrete Applied Mathematics, v.23 n.2, p.103-123, May 1989 [doi>10.1016/0166-218X(89)90022-X]
	29	M. C. Heydemann , J. C. Meyer , J. Opatrny , D. Sotteau, Forwarding indices of k-connected graphs, Discrete Applied Mathematics, 37-38, p.287-296, July 15, 1992 [doi>10.1016/0166-218X(92)90140-6]
	30	HEYDEMANN, M.C., MEYER, J.C., AND SOTTEAU, D. 1994. Forwarding indices of consistent routings and their complexity. Networks 24, 75-82.
	31	Hu, T.C. 1963. Multicommodity network flows. Oper. Res. 11, 3, 344-360.
	32	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.
	33	Anil Kamath , Omri Palmon, Improved interior point algorithms for exact and approximate solution of multicommodity flow problems, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.502-511, January 22-24, 1995, San Francisco, California, United States
	34	M Kirousis , C H Papadimitriou, Searching and pebbling, Theoretical Computer Science, v.47 n.2, p.205-218, Nov. 1986
	35	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.
	36	Philip N. Klein , Serge A. Plotkin , Satish Rao , Éva Tardos, Approximation algorithms for Steiner and directed multicuts, Journal of Algorithms, v.22 n.2, p.241-269, Feb. 1997 [doi>10.1006/jagm.1996.0833]
	37	Philip Klein , Serge Plotkin , Clifford Stein , Eva Tardos, Faster Approximation Algorithms for the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts, SIAM Journal on Computing, v.23 n.3, p.466-487, June 1994 [doi>10.1137/S0097539792241175]
	38	KLEIN, P., RAO, S., AGRAWAL, A., AND RAVI, R. 1995. Approximation through multicommodity flow. Combinatorica 15, 187-202.
	39	Philip Klein , Serge A. Plotkin , Satish Rao, Excluded minors, network decomposition, and multicommodity flow, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.682-690, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167261]
	40	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.
	41	Kevin Lang , Satish Rao, Finding near-optimal cuts: an empirical evaluation, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.212-221, January 25-27, 1993, Austin, Texas, United States
	42	Frank Thomson Leighton, Complexity issues in VLSI: optimal layouts for the shuffle-exchange graph and other networks, MIT Press, Cambridge, MA, 1983
	43	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.
	44	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.).
	45	Tom Leighton , Satish Rao , Aravind Srinivasan, Multicommodity Flow and Circuit Switching, Proceedings of the Thirty-First Annual Hawaii International Conference on System Sciences-Volume 7, p.459, January 06-09, 1998 [doi>10.1109/HICSS.1998.649241]
	46	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.
	47	Tom Leighton , Fillia Makedon , Serge Plotkin , Clifford Stein , Éva Tardos , Spyros Tragoudas, Fast approximation algorithms for multicommodity flow problems, Journal of Computer and System Sciences, v.50 n.2, p.228-243, April 1995
	48	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.
	49	T. Leighton , B. Maggs, Fast algorithms for finding O(congestion+dilation) packet routing schedules, Proceedings of the 28th Hawaii International Conference on System Sciences (HICSS'95), p.555, January 04-07, 1995
	50	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.
	51	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.
	52	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.
	53	LINIAL, N., LONDON, E., AND RABINOVICH, f. 1995. The geometry of graphs and some of its algorithmic applications. Combinatorica 15, 215-245.
	54	LIPTON, J. AND TARJAN, R.E. 1979. A separator theorem for planar graphs. SIAM J. Appl. Math. 36, 2 (Apr.), 177-189.
	55	LOMONOSOV, M.V. 1985. Combinatorial approaches to multiflow problems. Disc. Appl. Math. 11, 1-94.
	56	Lov#.sz, L. 1991. Random walk on graphs: A survey. Tech. Rep. Dept. Computer Science, Yale Univ., New Haven, Conn.
	57	MARGULIS, G.A. 1973. Explicit constructions of concentrators. Prob. Inf. Trans. 9, 325-332.
	58	MATULA, D. W. AND SHAHROKHI, F. 1986. The maximum concurrent flow problem and sparsest cuts. Tech. Rep. Southern Methodist Univ., Dallas, Tex.
	59	OKAMURA, H. AND SEYMOUR, P.D. 1981. Multicommodity flows in planar graphs. J. Combin. Theory, Ser. B 31, 75-81.
	60	PAPERNOV, B.A. 1990. Feasibility of multicommodity flows (in Russian). In Studies in Discrete Optimization, A. A. Friedman, ed. New York, pp. 17-34.
	61	James K. Park , Cynthia A. Phillips, Finding minimum-quotient cuts in planar graphs, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.766-775, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167284]
	62	David Peleg , Eli Upfal, The token distribution problem, SIAM Journal on Computing, v.18 n.2, p.229-243, April 1989 [doi>10.1137/0218015]
	63	Serge A. Plotkin , Éva Tardos, Improved bounds on the max-flow min-cut ratio for multicommodity flows, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.691-697, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167263]
	64	Prabhakar Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs, Journal of Computer and System Sciences, v.37 n.2, p.130-143, October 1988 [doi>10.1016/0022-0000(88)90003-7]
	65	Prabhakar Raghavan , Eli Upfal, Efficient routing in all-optical networks, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.134-143, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195119]
	66	Satish B. Rao, Faster algorithms for finding small edge cuts in planar graphs, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.229-240, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129735]
	67	R. Ravi , Ajit Agrawal , Philip Klein, Ordering problems approximated: single-processor scheduling and interval graph completion, Proceedings of the 18th international colloquium on Automata, languages and programming, p.751-762, June 1991, Madrid, Spain
	68	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.
	69	SEYMOUR, P.D. 1995. Packing directed circuits fractionally. Combinatorica 15, 281-288.
	70	Farhad Shahrokhi , D. W. Matula, The maximum concurrent flow problem, Journal of the ACM (JACM), v.37 n.2, p.318-334, April 1990 [doi>10.1145/77600.77620]
	71	David B. Shmoys, Cut problems and their application to divide-and-conquer, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
	72	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.
	73	Alistair Sinclair, Algorithms for random generation and counting: a Markov chain approach, Birkhauser Verlag, Basel, Switzerland, 1993
	74	Alistair Sinclair , Mark Jerrum, Approximate counting, uniform generation and rapidly mixing Markov chains, Information and Computation, v.82 n.1, p.93-133, July 1989 [doi>10.1016/0890-5401(89)90067-9]
	75	Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
	76	Spyros Tragoudas, VLSI partitioning approximation algorithms based on multicommodity flow and other techniques, University of Texas at Dallas, Richardson, TX, 1991
	77	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.
	78	VALIANT, k.1981. Universality considerations in VLSI circuits. IEEE Trans. Comput. C-30, 2, 135-140.
	79	Ching-Wei Yeh , Chung-Kuan Cheng , Ting-Ting Y. Lin, A probabilistic multicommodity-flow solution to circuit clustering problems, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.428-431, November 1992, Santa Clara, California, United States

CITED BY 85

	Elliot Anshelevich , David Kempe , Jon Kleinberg, Stability of load balancing algorithms in dynamic adversarial systems, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Uriel Feige, Relations between average case complexity and approximation complexity, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Guy Even , Joseph Seffi Naor , Satish Rao , Baruch Schieber, Divide-and-conquer approximation algorithms via spreading metrics, Journal of the ACM (JACM), v.47 n.4, p.585-616, July 2000
	Guy Even , Sudipto Guha , Baruch Schieber, Improved approximations of crossings in graph drawings, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.296-305, May 21-23, 2000, Portland, Oregon, United States
	Uriel Feige , Robert Krauthgamer , Kobbi Nissim, Approximating the minimum bisection size (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.530-536, May 21-23, 2000, Portland, Oregon, United States
	Josep Díaz , Jordi Petit , Maria Serna, A survey of graph layout problems, ACM Computing Surveys (CSUR), v.34 n.3, p.313-356, September 2002
	Jiangzhuo Chen , Rajmohan Rajaraman , Ravi Sundaram, Meet and merge: approximation algorithms for confluent flows, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Uriel Feige , Orly Yahalom, On the complexity of finding balanced oneway cuts, Information Processing Letters, v.87 n.1, p.1-5, 16 July 2003
	Christos Gkantsidis , Milena Mihail , Amin Saberi, Conductance and congestion in power law graphs, ACM SIGMETRICS Performance Evaluation Review, v.31 n.1, June 2003
	Yuri Rabinovich, On average distortion of embedding metrics into the line and into L₁, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Daniel Golovin , Viswanath Nagarajan , Mohit Singh, Approximating the k-multicut problem, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.621-630, January 22-26, 2006, Miami, Florida
	Paul Bonsma, Sparsest cuts and concurrent flows in product graphs, Discrete Applied Mathematics, v.136 n.2-3, p.173-182, 15 February 2004
	Joseph (Seffi) Naor , Roy Schwartz, The directed circular arrangement problem, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Claudson F. Bornstein , Santosh Vempala, Flow metrics, Theoretical Computer Science, v.321 n.1, p.13-24, June 16, 2004
	V. Bouchitté , D. Kratsch , H. Müller , I. Todinca, On treewidth approximations, Discrete Applied Mathematics, v.136 n.2-3, p.183-196, 15 February 2004
	Aaron Archer , Jittat Fakcharoenphol , Chris Harrelson , Robert Krauthgamer , Kunal Talwar , Éva Tardos, Approximate classification via earthmover metrics, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Eyal Amir , Robert Krauthgamer , Satish Rao, Constant factor approximation of vertex-cuts in planar graphs, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Gruia Calinescu , Cristina G. Fernandes , Bruce Reed, Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width, Journal of Algorithms, v.48 n.2, p.333-359, September 2003
	Petr Kolman , Christian Scheideler, Improved bounds for the unsplittable flow problem, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.184-193, January 06-08, 2002, San Francisco, California
	Ravi Kannan , Santosh Vempala , Adrian Vetta, On clusterings: Good, bad and spectral, Journal of the ACM (JACM), v.51 n.3, p.497-515, May 2004
	David Kempe , Frank McSherry, A decentralized algorithm for spectral analysis, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Vincenzo Liberatore, Circular arrangements and cyclic broadcast scheduling, Journal of Algorithms, v.51 n.2, p.185-215, May 2004
	Chandra Chekuri , Sanjeev Khanna , F. Bruce Shepherd, The all-or-nothing multicommodity flow problem, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Sanjeev Arora , Satish Rao , Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.222-231, June 13-16, 2004, Chicago, IL, USA
	Daniel A. Spielman , Shang-Hua Teng, Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Petr Kolman , Jiří Matoušek, Crossing number, pair-crossing number, and expansion, Journal of Combinatorial Theory Series B, v.92 n.1, p.99-113, September 2004
	Konstantin Andreev , Harald Räcke, Balanced graph partitioning, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Joseph (Seffi) Naor , Roy Schwartz, Balanced metric labeling, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Amit Agarwal , Moses Charikar , Konstantin Makarychev , Yury Makarychev, O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Chandra Chekuri , Sanjeev Khanna , F. Bruce Shepherd, Multicommodity flow, well-linked terminals, and routing problems, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Uriel Feige , MohammadTaghi Hajiaghayi , James R. Lee, Improved approximation algorithms for minimum-weight vertex separators, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Shuchi Chawla , Anupam Gupta , Harald Räcke, Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Micah Adler , Nicholas J. A. Harvey , Kamal Jain , Robert Kleinberg , April Rasala Lehman, On the capacity of information networks, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.241-250, January 22-26, 2006, Miami, Florida
	Robert Krauthgamer , Yuval Rabani, Improved lower bounds for embeddings into L₁, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1010-1017, January 22-26, 2006, Miami, Florida
	James Aspnes , Kevin Chang , Aleksandr Yampolskiy, Inoculation strategies for victims of viruses and the sum-of-squares partition problem, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Moses Charikar , Mohammad Taghi Hajiaghayi , Howard Karloff , Satish Rao, l²₂ spreading metrics for vertex ordering problems, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1018-1027, January 22-26, 2006, Miami, Florida
	Sanjeev Arora , Eden Chlamtac, New approximation guarantee for chromatic number, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Rohit Khandekar , Satish Rao , Umesh Vazirani, Graph partitioning using single commodity flows, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Michael Elkin , Yuval Emek , Daniel A. Spielman , Shang-Hua Teng, Lower-stretch spanning trees, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	M. T. Hajiaghayi , Tom Leighton, On the max-flow min-cut ratio for directed multicommodity flows, Theoretical Computer Science, v.352 n.1, p.318-321, 7 March 2006
	Jiangzhuo Chen , Rajmohan Rajaraman , Ravi Sundaram, Meet and merge: approximation algorithms for confluent flows, Journal of Computer and System Sciences, v.72 n.3, p.468-489, May 2006
	Antonio Capone , Luigi Fratta , Fabio Martignon, Dynamic online QoS routing schemes: performance and bounds, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.7, p.966-981, 15 May 2006
	Mohammad Taghi Hajiaghayi , Harald Räcke, An O(√n)-approximation algorithm for directed sparsest cut, Information Processing Letters, v.97 n.4, p.156-160, 28 February 2006
	Maurizio Bruglieri , Matthias Ehrgott , Horst W. Hamacher , Francesco Maffioli, An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints, Discrete Applied Mathematics, v.154 n.9, p.1344-1357, 1 June 2006
	Milena Mihail , Christos Papadimitriou , Amin Saberi, On certain connectivity properties of the internet topology, Journal of Computer and System Sciences, v.72 n.2, p.239-251, March 2006
	Nicholas J. A. Harvey , Robert Kleinberg , April Rasala Lehman, On the capacity of information networks, IEEE/ACM Transactions on Networking (TON), v.14 n.SI, p.2345-2364, June 2006
	Nikhil R. Devanur , Subhash A. Khot , Rishi Saket , Nisheeth K. Vishnoi, Integrality gaps for sparsest cut and minimum linear arrangement problems, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	David S. Johnson, The NP-completeness column: The many limits on approximation, ACM Transactions on Algorithms (TALG), v.2 n.3, p.473-489, July 2006
	Kevin J. Lang , Reid Andersen, Finding dense and isolated submarkets in a sponsored search spending graph, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal
	Petr Kolman , Christian Scheideler, Simple on-line algorithms for the maximum disjoint paths problem, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.38-47, July 2001, Crete Island, Greece
	Christina Fragouli , Tarik Tabet, On conditions for constant throughput in wireless networks, ACM Transactions on Sensor Networks (TOSN), v.2 n.3, p.359-379, August 2006
	James Aspnes , Kevin Chang , Aleksandr Yampolskiy, Inoculation strategies for victims of viruses and the sum-of-squares partition problem, Journal of Computer and System Sciences, v.72 n.6, p.1077-1093, September 2006
	Erik D. Demaine , Dotan Emanuel , Amos Fiat , Nicole Immorlica, Correlation clustering in general weighted graphs, Theoretical Computer Science, v.361 n.2, p.172-187, 1 September 2006
	Julia Chuzhoy , Sanjeev Khanna, Hardness of cut problems in directed graphs, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Chandra Chekuri , Sanjeev Khanna , F. Bruce Shepherd, Edge-disjoint paths in Planar graphs with constant congestion, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Ittai Abraham , Yair Bartal , Ofer Neimany, Advances in metric embedding theory, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Uriel Feige , Mohammad Mahdian, Finding small balanced separators, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Matthew Andrews , Lisa Zhang, Logarithmic hardness of the undirected edge-disjoint paths problem, Journal of the ACM (JACM), v.53 n.5, p.745-761, September 2006
	Sushmita Gupta, Feedback arc set problem in bipartite tournaments, Information Processing Letters, v.105 n.4, p.150-154, February, 2008
	Petr Kolman , Christian Scheideler, Improved bounds for the unsplittable flow problem, Journal of Algorithms, v.61 n.1, p.20-44, September, 2006
	David Kempe , Frank McSherry, A decentralized algorithm for spectral analysis, Journal of Computer and System Sciences, v.74 n.1, p.70-83, February, 2008
	Lorenzo Orecchia , Leonard J. Schulman , Umesh V. Vazirani , Nisheeth K. Vishnoi, On partitioning graphs via single commodity flows, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Shuchi Chawla , Anupam Gupta , Harald Räcke, Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut, ACM Transactions on Algorithms (TALG), v.4 n.2, p.1-18, May 2008
	Adi Avidor , Michael Langberg, The multi-multiway cut problem, Theoretical Computer Science, v.377 n.1-3, p.35-42, May, 2007
	Erik D. Demaine , MohammadTaghi Hajiaghayi , Bojan Mohar, Approximation algorithms via contraction decomposition, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.278-287, January 07-09, 2007, New Orleans, Louisiana
	Julia Chuzhoy , Sanjeev Khanna, Polynomial flow-cut gaps and hardness of directed cut problems, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Yinyu Ye , Jiawei Zhang, Approximation of Dense-n/2-Subgraph and the Complement of Min-Bisection, Journal of Global Optimization, v.25 n.1, p.55-73, January 2003
	Navin Goyal , Neil Olver , F B. Shepherd, The VPN conjecture is true, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Erik D. Demaine , MohammadTaghi Hajiaghayi , Hamid Mahini , Morteza Zadimoghaddam, The price of anarchy in network creation games, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Jure Leskovec , Kevin J. Lang , Anirban Dasgupta , Michael W. Mahoney, Statistical properties of community structure in large social and information networks, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China
	Rajat Bhattacharjee , Ashish Goel, Algorithms and incentives for robust ranking, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.425-433, January 07-09, 2007, New Orleans, Louisiana
	Henning Bruhn , Jakub Černý , Alexander Hall , Petr Kolman, Single source multiroute flows and cuts on uniform capacity networks, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.855-863, January 07-09, 2007, New Orleans, Louisiana
	Chandra Chekuri, Routing and network design with robustness to changing or uncertain traffic demands, ACM SIGACT News, v.38 n.3, September 2007
	Jianer Chen , Yang Liu , Songjian Lu , Barry O'sullivan , Igor Razgon, A fixed-parameter algorithm for the directed feedback vertex set problem, Journal of the ACM (JACM), v.55 n.5, p.1-19, October 2008
	Sanjeev Arora , Satish Rao , Umesh Vazirani, Geometry, flows, and graph-partitioning algorithms, Communications of the ACM, v.51 n.10, October 2008
	Abdallah Khreishah , Chih-Chun Wang , Ness B. Shroff, Capacity regions for multiple unicast flows using inter-session network coding, Proceedings of the 3rd international conference on Wireless internet, October 22-24, 2007, Austin, Texas
	Julia Chuzhoy , Sanjeev Khanna, Polynomial flow-cut gaps and hardness of directed cut problems, Journal of the ACM (JACM), v.56 n.2, p.1-28, April 2009
	Navin Goyal , Luis Rademacher , Santosh Vempala, Expanders via random spanning trees, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.576-585, January 04-06, 2009, New York, New York
	Robert Krauthgamer , Joseph (Seffi) Naor , Roy Schwartz, Partitioning graphs into balanced components, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.942-949, January 04-06, 2009, New York, New York
	Sanjeev Arora , Satish Rao , Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning, Journal of the ACM (JACM), v.56 n.2, p.1-37, April 2009
	James R. Lee , Anastasios Sidiropoulos, On the geometry of graphs with a forbidden minor, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Shirish Karande , Zheng Wang , Hamid R. Sadjadpour , Jose Joaquin Garcia-Luna-Aceves, On the multicast throughput capacity of network coding in wireless ad-hoc networks, Proceedings of the 2nd ACM international workshop on Foundations of wireless ad hoc and sensor networking and computing, May 18-18, 2009, New Orleans, Louisiana, USA
	Rohit Khandekar , Satish Rao , Umesh Vazirani, Graph partitioning using single commodity flows, Journal of the ACM (JACM), v.56 n.4, p.1-15, June 2009
	Bill MacCartney , Sheila McIlraith , Eyal Amir , Tomás E. Uribe, Practical partition-based theorem proving for large knowledge bases, Proceedings of the 18th international joint conference on Artificial intelligence, p.89-96, August 09-15, 2003, Acapulco, Mexico
	Martin Holzer , Frank Schulz , Dorothea Wagner , Grigorios Prasinos , Christos Zaroliagis, Engineering planar separator algorithms, Journal of Experimental Algorithmics (JEA), 14, August 2009

INDEX TERMS

Primary Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms

Keywords:
VLSI layout, approximation algorithms, divide and conquer, graph bisection, graph partitioning, maximum flow, minimum cut, muticommocity flow, routing

REVIEW

"Patrick J. Ryan : Reviewer"

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, t more...

Collaborative Colleagues:

Tom Leighton: colleagues

Satish Rao: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player