Rounding algorithms for a geometric embedding of minimum multiway cut

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Rounding algorithms for a geometric embedding of minimum multiway cut

Full text

Pdf (855 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-first annual ACM symposium on Theory of computing table of contents

Atlanta, Georgia, United States

Pages: 668 - 678

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

David R. Karger	MIT Laboratory for Computer Science, Cambridge, MA
Philip Klein	Brown University
Cliff Stein	Dartmouth College
Mikkel Thorup	AT&T Labs-Research, Shannon Laboratory, 180 Park Avenue, Florham Park, NJ
Neal E. Young	Dartmouth College

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 27, Citation Count: 12

Additional Information:

references cited by index terms 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/301250.301430 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	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]
	2	Gruia Călinescu , Howard Karloff , Yuval Rabani, An improved approximation algorithm for multiway cut, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.48-52, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276711]
	3	William H. Cunningham , Lawrence Tang, Optimal 3-Terminal Cuts and Linear Programming, Proceedings of the 7th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.114-125, June 09-11, 1999
	4	E. Dahlhaus , D. S. Johnson , C. H. Papadimitriou , P. D. Seymour , M. Yannakakis, The Complexity of Multiterminal Cuts, SIAM Journal on Computing, v.23 n.4, p.864-894, Aug. 1994 [doi>10.1137/S0097539792225297]
	5	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
	6	Michel X. Goemans , David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM), v.42 n.6, p.1115-1145, Nov. 1995 [doi>10.1145/227683.227684]
	7	T. Leighton and S. Rao. An approximate max-flow mincut 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, 1988.
	8	Nathan Linial, Eran London, and Yuri Rabinovich. The geometry of graphs and some of its algorithmic applications. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pages 577-59t, Santa Fe, New Mexico, 20-22 November 1994. IEEE.

CITED BY 12

	Chandra Chekuri , Sanjeev Khanna , Joseph Naor , Leonid Zosin, Approximation algorithms for the metric labeling problem via a new linear programming formulation, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.109-118, January 07-09, 2001, Washington, D.C., United States
	Anupam Gupta , Éva Tardos, A constant factor approximation algorithm for a class of classification problems, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.652-658, May 21-23, 2000, Portland, Oregon, United States
	Gruia Calinescu , Howard Karloff , Yuval Rabani, Approximation algorithms for the 0-extension problem, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.8-16, January 07-09, 2001, Washington, D.C., United States
	Jon Kleinberg , Éva Tardos, Approximation algorithms for classification problems with pairwise relationships: metric labeling and Markov random fields, Journal of the ACM (JACM), v.49 n.5, p.616-639, September 2002
	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
	Liang Zhao , Hiroshi Nagamochi , Toshihide Ibaraki, On generalized greedy splitting algorithms for multiway partition problems, Discrete Applied Mathematics, v.143 n.1-3, p.130-143, 30 September 2004
	Jittat Fakcharoenphol , Chris Harrelson , Satish Rao , Kunal Talwar, An improved approximation algorithm for the 0-extension problem, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Naveen Garg , Vijay V. Vazirani , Mihalis Yannakakis, Multiway cuts in node weighted graphs, Journal of Algorithms, v.50 n.1, p.49-61, January 2004
	Moses Charikar , Venkatesan Guruswami , Anthony Wirth, Clustering with qualitative information, Journal of Computer and System Sciences, v.71 n.3, p.360-383, October 2005
	Roee Engelberg , Jochen Könemann , Stefano Leonardi , Joseph (Seffi) Naor, Cut problems in graphs with a budget constraint, Journal of Discrete Algorithms, v.5 n.2, p.262-279, June, 2007
	Songqiao Han , Shensheng Zhang , Jian Cao , Ye Wen , Yong Zhang, A resource aware software partitioning algorithm based on mobility constraints in pervasive grid environments, Future Generation Computer Systems, v.24 n.6, p.512-529, June, 2008
	Rajsekar Manokaran , Joseph (Seffi) Naor , Prasad Raghavendra , Roy Schwartz, Sdp gaps and ugc hardness for multiway cut, 0-extension, and metric labeling, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada