A constant factor approximation algorithm for a class of classification problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A constant factor approximation algorithm for a class of classification problems

Full text

Pdf (728 KB)

Source

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

Portland, Oregon, United States

Pages: 652 - 658

Year of Publication: 2000

ISBN:1-58113-184-4

Authors

Anupam Gupta	Computer Science Division, UC Berkeley, Berkeley, CA
Éva Tardos	Department of Computer Science, Cornell University, Ithaca, NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 34, 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/335305.335397 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	Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
	2	Yair Bartal, On approximating arbitrary metrices by tree metrics, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.161-168, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276725]
	3	Julian Besag. On the statistical analysis of dirty pictures. J. Roy. Statist. Soc. Ser. B, 48(3):259-302, 1986.
	4	Y. Boykov , O. Veksler , R. Zabih, Markov Random Fields with Efficient Approximations, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, p.648, June 23-25, 1998
	5	Yuri Boykov, Olga Veksler, and Ramin Zabih. Fast approximate energy minimization via graph cuts. In Proceedings of the 7th IEEE International Conference on Computer Vision, volume 1, pages 377-384, 1999.
	6	Yuri Boykov , Olga Veksler , Ramin Zabih, A New Algorithm for Energy Minimization with Discontinuities, Proceedings of the Second International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition, p.205-220, July 26-29, 1999
	7	Leo Breiman, Jerome H. Friedman, Richard A. Olshen, and Charles J. Stone. Classification and regression trees. Wadsworth Advanced Books and Software, Belmont, CA, 1984.
	8	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]
	9	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
	10	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]
	11	Michel Marie Deza and Monique Laurent. Geometry of Cuts and Metrics. Springer Verlag, 1997.
	12	Thomas G. Dietterich. Machine learning research: Four current directions. AI Magazine, 18(4):97-136, 1997.
	13	Péter L. Erdős , László A. Székely, Evolutionary trees: an integer multicommodity max-flow—min-cut theorem, Advances in Applied Mathematics, v.13 n.4, p.375-389, Dec. 1992 [doi>10.1016/0196-8858(92)90017-Q]
	14	Stuart Geman and Donald Geman. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 6:721-741, 1984.
	15	D. Greig, B.T. Porteous, and A. Seheult. Exact maximum a posteriori estimation for binary images. J. Royal Statistical Society B, 51(2):271-279, 1989.
	16	H. Ishikawa , D. Geiger, Segmentation by Grouping Junctions, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, p.125, June 23-25, 1998
	17	David R. Karger , Philip Klein , Cliff Stein , Mikkel Thorup , Neal E. Young, Rounding algorithms for a geometric embedding of minimum multiway cut, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.668-678, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301430]
	18	Alexander V. Karzanov, Minimum 0-extensions of graph metrics, European Journal of Combinatorics, v.19 n.1, p.71-101, Jan., 1998 [doi>10.1006/eujc.1997.0154]
	19	Jon Kleinberg , Eva Tardos, Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.14, October 17-18, 1999
	20	Sébastien Roy , Ingemar J. Cox, A Maximum-Flow Formulation of the N-Camera Stereo Correspondence Problem, Proceedings of the Sixth International Conference on Computer Vision, p.492, January 04-07, 1998
	21	Olga Veksler , Ramin Zabih, Efficient graph-based energy minimization methods in computer vision, 1999

CITED BY 12

	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
	Dorit S. Hochbaum, An efficient algorithm for image segmentation, Markov random fields and related problems, Journal of the ACM (JACM), v.48 n.4, p.686-701, July 2001
	Moses S. Charikar, Similarity estimation techniques from rounding algorithms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	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
	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
	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
	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
	Howard Karloff , Subhash Khot , Aranyak Mehta , Yuval Rabani, On earthmover distance, metric labeling, and 0-extension, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Evandro C. Bracht , Luis , A. A. Meira , F. K. Miyazawa, A greedy approximation algorithm for the uniform metric labeling problem analyzed by a primal-dual technique, Journal of Experimental Algorithmics (JEA), 10, 2005
	Petra Schuurman , Tjark Vredeveld, Performance Guarantees of Local Search for Multiprocessor Scheduling, INFORMS Journal on Computing, v.19 n.1, p.52-63, January 2007
	Nikos Komodakis , Georgios Tziritas, Approximate Labeling via Graph Cuts Based on Linear Programming, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.29 n.8, p.1436-1453, August 2007
	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