Approximation schemes for Euclidean k-medians and related problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximation schemes for Euclidean k-medians and related problems

Full text

Pdf (878 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirtieth annual ACM symposium on Theory of computing table of contents

Dallas, Texas, United States

Pages: 106 - 113

Year of Publication: 1998

ISBN:0-89791-962-9

Authors

Sanjeev Arora	Princeton University
Prabhakar Raghavan	IBM Almaden Research Center, 650 Harry Road, San Jose CA
Satish Rao	NEC Research Institute, Princeton, NJ

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 83, Citation Count: 49

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/276698.276718 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	S. Arora, Polynomial time approximation schemes for Euclidean TSP and other geometric problems, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.2, October 14-16, 1996
	2	S. Arora, Nearly linear time approximation schemes for Euclidean TSP and other geometric problems, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.554, October 19-22, 1997
	3	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
	4	Marshall Bern , David Eppstein, Approximation algorithms for geometric problems, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
	5	F. Chudak. Improved approximation algorithms for uncapacitated facility location. Submitted for publication.
	6	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
	7	D.S. Hochbaum. Heuristics for the fixed cost median problem. Math. Programming, 22~ 148-162~ 1982.
	8	Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
	9	Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
	10	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]
	11	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]
	12	O. L. Mangasarian, Mathematical Programming in Data Mining, Data Mining and Knowledge Discovery, v.1 n.2, p.183-201, 1997 [doi>10.1023/A:1009735908398]
	13	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]

CITED BY 49

	Kamal Jain , Vijay V. Vazirani, Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation, Journal of the ACM (JACM), v.48 n.2, p.274-296, March 2001
	Mihai Bādoiu , Sariel Har-Peled , Piotr Indyk, Approximate clustering via core-sets, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Tapas Kanungo , David M. Mount , Nathan S. Netanyahu , Christine D. Piatko , Ruth Silverman , Angela Y. Wu, A local search approximation algorithm for k-means clustering, Proceedings of the eighteenth annual symposium on Computational geometry, p.10-18, June 05-07, 2002, Barcelona, Spain
	Moses Charikar , Sudipto Guha , Éva Tardos , David B. Shmoys, A constant-factor approximation algorithm for the k-median problem, Journal of Computer and System Sciences, v.65 n.1, p.129-149, August 2002
	Sanjeev Arora, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, Journal of the ACM (JACM), v.45 n.5, p.753-782, Sept. 1998
	Rafail Ostrovsky , Yuval Rabani, Polynomial-time approximation schemes for geometric min-sum median clustering, Journal of the ACM (JACM), v.49 n.2, p.139-156, March 2002
	Tapas Kanungo , David M. Mount , Nathan S. Netanyahu , Christine Piatko , Ruth Silverman , Angela Y. Wu, The analysis of a simple k-means clustering algorithm, Proceedings of the sixteenth annual symposium on Computational geometry, p.100-109, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Leonard J. Schulman, Clustering for edge-cost minimization (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.547-555, May 21-23, 2000, Portland, Oregon, United States
	Konstantinos Kalpakis , Koustuv Dasgupta , Ouri Wolfson, Optimal Placement of Replicas in Trees with Read, Write, and Storage Costs, IEEE Transactions on Parallel and Distributed Systems, v.12 n.6, p.628-637, June 2001
	S. Bespamyatnikh , B. Bhattacharya , D. Kirkpatrick , M. Segal, Mobile facility location (extended abstract), Proceedings of the 4th international workshop on Discrete algorithms and methods for mobile computing and communications, p.46-53, August 11-11, 2000, Boston, Massachusetts, United States
	David B. Shmoys, Approximation algorithms for clustering problems, Proceedings of the twelfth annual conference on Computational learning theory, p.100-101, July 07-09, 1999, Santa Cruz, California, United States
	Artur Czumaj , Andrzej Lingas, On approximability of the minimum-cost k-connected spanning subgraph problem, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.281-290, January 17-19, 1999, Baltimore, Maryland, United States
	P. Drineas , Alan Frieze , Ravi Kannan , Santosh Vempala , V. Vinay, Clustering in large graphs and matrices, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.291-299, January 17-19, 1999, Baltimore, Maryland, United States
	Moses Charikar , Samir Khuller , David M. Mount , Giri Narasimhan, Algorithms for facility location problems with outliers, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.642-651, January 07-09, 2001, Washington, D.C., United States
	Tapas Kanungo , David M. Mount , Nathan S. Netanyahu , Christine Piatko , Ruth Silverman , Angela Y. Wu, Computing nearest neighbors for moving points and applications to clustering, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.931-932, January 17-19, 1999, Baltimore, Maryland, United States
	Pankaj K. Agarwal , Micha Sharir, Efficient algorithms for geometric optimization, ACM Computing Surveys (CSUR), v.30 n.4, p.412-458, Dec. 1998
	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
	Pankaj K. Agarwal , Cecilia M. Procopiuc, Approximation algorithms for projective clustering, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.538-547, January 09-11, 2000, San Francisco, California, United States
	Venkatesan Guruswami , Piotr Indyk, Embeddings and non-approximability of geometric problems, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	W. Fernandez de la Vega , Marek Karpinski , Claire Kenyon , Yuval Rabani, Approximation schemes for clustering problems, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Moses Charikar , Liadan O'Callaghan , Rina Panigrahy, Better streaming algorithms for clustering problems, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Kunal Talwar, Bypassing the embedding: algorithms for low dimensional metrics, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Sariel Har-Peled , Soham Mazumdar, On coresets for k-means and k-median clustering, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Tapas Kanungo , David M. Mount , Nathan S. Netanyahu , Christine D. Piatko , Ruth Silverman , Angela Y. Wu, A local search approximation algorithm for k-means clustering, Computational Geometry: Theory and Applications, v.28 n.2-3, p.89-112, June 2004
	Adam Meyerson , Liadan O'Callaghan , Serge Plotkin, A k-Median Algorithm with Running Time Independent of Data Size, Machine Learning, v.56 n.1-3, p.61-87
	Tapas Kanungo , David M. Mount , Nathan S. Netanyahu , Christine D. Piatko , Ruth Silverman , Angela Y. Wu, An Efficient k-Means Clustering Algorithm: Analysis and Implementation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.7, p.881-892, July 2002
	Sudipto Guha , Adam Meyerson , Nina Mishra , Rajeev Motwani , Liadan O'Callaghan, Clustering Data Streams: Theory and Practice, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.515-528, March 2003
	Aristides Gionis , Heikki Mannila, Finding recurrent sources in sequences, Proceedings of the seventh annual international conference on Research in computational molecular biology, p.123-130, April 10-14, 2003, Berlin, Germany
	Hanson Zhou , David Woodruff, Clustering via matrix powering, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France
	Sariel Har-Peled , Akash Kushal, Smaller coresets for k-median and k-means clustering, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	Ke Chen, On k-Median clustering in high dimensions, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1177-1185, January 22-26, 2006, Miami, Florida
	Esther M. Arkin , Gill Barequet , Joseph S. B. Mitchell, Algorithms for two-box covering, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Sergey Bereg , Binay Bhattacharya , David Kirkpatrick , Michael Segal, Competitive algorithms for maintaining a mobile center, Mobile Networks and Applications, v.11 n.2, p.177-186, April 2006
	Surajit Chaudhuri , Ashish Kumar Gupta , Vivek Narasayya, Compressing SQL workloads, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin
	Sören Laue , Domagoj Matijević, Approximating k-hop minimum spanning trees in Euclidean metrics, Information Processing Letters, v.107 n.3-4, p.96-101, July, 2008
	Luis A. A. Meira , Flávio K. Miyazawa, A continuous facility location problem and its application to a clustering problem, Proceedings of the 2008 ACM symposium on Applied computing, March 16-20, 2008, Fortaleza, Ceara, Brazil
	Helmut Alt , Esther M. Arkin , Hervé Brönnimann , Jeff Erickson , Sándor P. Fekete , Christian Knauer , Jonathan Lenchner , Joseph S. B. Mitchell , Kim Whittlesey, Minimum-cost coverage of point sets by disks, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Fang Bian , David Kempe , Ramesh Govindan, Utility based sensor selection, Proceedings of the fifth international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA
	Jan Remy , Angelika Steger, A quasi-polynomial time approximation scheme for minimum weight triangulation, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	V. Estivill-Castro , J. Yang, Fast and Robust General Purpose Clustering Algorithms, Data Mining and Knowledge Discovery, v.8 n.2, p.127-150, March 2004
	Manghui Tu , Zhonghang Xia , Peng Li , Nasser Tadayon, Allocation of partitioned data by using a neural network based approach, Neurocomputing, v.72 n.4-6, p.1000-1011, January, 2009
	Andrea E. F. Clementi , Miriam Di Ianni , Massimo Lauria , Angelo Monti , Gianluca Rossi , Riccardo Silvestri, On the bounded-hop MST problem on random Euclidean instances, Theoretical Computer Science, v.384 n.2-3, p.161-167, October, 2007
	Qishi Wu , Nageswara S. V. Rao , Xiaojiang Du , S. Sitharama Iyengar , Vijay K. Vaishnavi, On efficient deployment of sensors on planar grid, Computer Communications, v.30 n.14-15, p.2721-2734, October, 2007
	T-H. Hubert Chan , Anupam Gupta, Approximating TSP on metrics with bounded global growth, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.690-699, January 20-22, 2008, San Francisco, California
	Kyriakos Mouratidis , Dimitris Papadias , Spiros Papadimitriou, Tree-based partition querying: a methodology for computing medoids in large spatial datasets, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.4, p.923-945, July 2008
	Gaurav Sharma , Ravi R. Mazumdar, A case for hybrid sensor networks, IEEE/ACM Transactions on Networking (TON), v.16 n.5, p.1121-1132, October 2008
	Maria-Florina Balcan , Avrim Blum , Anupam Gupta, Approximate clustering without the approximation, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1068-1077, January 04-06, 2009, New York, New York
	Jan Remy , Angelika Steger, A quasi-polynomial time approximation scheme for minimum weight triangulation, Journal of the ACM (JACM), v.56 n.3, p.1-47, May 2009
	Ariel D. Procaccia , Moshe Tennenholtz, Approximate mechanism design without money, Proceedings of the tenth ACM conference on Electronic commerce, July 06-10, 2009, Stanford, California, USA