Approximation algorithms for clustering problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximation algorithms for clustering problems

Full text

Pdf (278 KB)

Source

Annual Workshop on Computational Learning Theory archive
Proceedings of the twelfth annual conference on Computational learning theory table of contents

Santa Cruz, California, United States

Pages: 100 - 101

Year of Publication: 1999

ISBN:1-58113-167-4

Author

David B. Shmoys

School of Operations Research & Industrial Engineering and Department of Computer Science, Cornell University, Ithaca, NY

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence
Univ. of California, : University of California at Santa Cruz

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 35, Citation Count: 0

Additional Information:

references index terms collaborative colleagues

Tools and Actions:	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/307400.307417 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	Sanjeev Arora , Prabhakar Raghavan , Satish Rao, Approximation schemes for Euclidean k-medians and related problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.106-113, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276718]
	2	M. L. Balinksi. On finding integer solutions to linear programs. In Proceedings of the IBM Scientific Computing Symposium on Combinatorial Problems, pages 225-248. IBM, 1966.
	3	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]
	4	Moses Charikar , Chandra Chekuri , Ashish Goel , Sudipto Guha, Rounding via trees: deterministic approximation algorithms for group Steiner trees and k-median, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.114-123, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276719]
	5	Moses Charikar , Sudipto Guha , Éva Tardos , David B. Shmoys, A constant-factor approximation algorithm for the k-median problem (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.1-10, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301257]
	6	Fabián A. Chudak, Improved Approximation Algorithms for Uncapitated Facility Location, Proceedings of the 6th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.180-194, June 22-24, 1998
	7	E Chudak and D. Shmoys. Improved approximation alcrt~;thmo fnv tha ~nt-anaoltat$ci fat-ii;h, !npatlnn nrc~h_ lem. Unpublished manuscript, 1998.
	8	Sudipto Guha , Samir Khuller, Greedy strikes back: improved facility location algorithms, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.649-657, January 25-27, 1998, San Francisco, California, United States
	9	D. S. Hochbaum. Heuristics for the fixed cost median problem. Math. Programming, 22:148-162, 1982.
	10	K. Jain and V. V. Vazirani. Primal-dual approximation algorithms for metric facility location and k-median problems. 1999.
	11	Madhukar R. Korupolu , C. Greg Plaxton , Rajmohan Rajaraman, Analysis of a local search heuristic for facility location problems, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.1-10, January 25-27, 1998, San Francisco, California, United States
	12	A.A. Kuehn and M. J. Hamburger. A heuristic program for locating warehouses. Management Sci., 9:643-666, l~9OJ.
	13	Jyh-Han Lin , Jeffrey Scott Vitter, Approximation algorithms for geometric median problems, Information Processing Letters, v.44 n.5, p.245-249, Dec. 21, 1992 [doi>10.1016/0020-0190(92)90208-D]
	14	Jyh-Han Lin , Jeffrey Scott Vitter, e-approximations with minimum packing constraint violation (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.771-782, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129787]
	15	A. S. Manne. Plant location under economies-of-scaledecentralization and computation. Management Sci., 11:213-235, 1964.
	16	David B. Shmoys , Éva Tardos , Karen Aardal, Approximation algorithms for facility location problems (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.265-274, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258600]
	17	J. E Stollsteimer. The effect of technical change and output expansion on the optimum number, size and location of pear marketing facilities in a California pear producing region. PhD thesis, University of California at Berkeley, Berkeley, Ca!ifornia, 1961:
	18	J. E Stollsteimer. A working model for plant numbers and locations. J. Farm Econom., 45:631-645, 1963.

INDEX TERMS

Primary Classification:
G. Mathematics of Computing

General Terms:
Theory, Verification

Collaborative Colleagues:

David B. Shmoys: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player