A constant-factor approximation algorithm for the k-median problem (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A constant-factor approximation algorithm for the k-median problem (extended abstract)

Full text

Pdf (879 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: 1 - 10

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

Moses Charikar	Stanford University, Stanford, CA
Sudipto Guha	Stanford University, Stanford, CA
Éva Tardos	Cornell University, Ithaca, NY
David B. Shmoys	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): 3, Downloads (12 Months): 45, Citation Count: 53

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.301257 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	Judit Bar-Ilan , Guy Kortsarz , David Peleg, How to allocate network centers, Journal of Algorithms, v.15 n.3, p.385-415, Nov. 1993 [doi>10.1006/jagm.1993.1047]
	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	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]
	5	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]
	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	F. Chudak and D. Shmoys. Improved approximation algorithms for the uncapacitated facility location problem. Unpublished manuscript, 1998.
	8	Fabián A. Chudak , David B. Shmoys, Improved approximation algorithms for a capacitated facility location problem, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.875-876, January 17-19, 1999, Baltimore, Maryland, United States
	9	G. Cornu~jols, G. L. Nemhauser, and L. A. Wolsey. The uncapacitated facility location problem. In P. Mirchandani and R. Francis, editors, Discrete Location Theory, pages 119- I71. John WiIey and Sons, Inc., New York, 1990.
	10	M. E. Dyer and A. M. Frieze. A simple heuristic for the p-center problem. Oper. Res. Lett., 3:285-288, 1985.
	11	T. F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoret. Comput. $ci., 38:293-306, 1985.
	12	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
	13	D. S. Hochbaum and D. B. Shmoys. A best possible approximation algorithm for the k-center problem. Math. Oper. Res., 10:180-184, 1985.
	14	O. Kariv and S. L. Hakimi. An algorithmic approach to network location problems, Part II: pmedians. SIAM J. Appl. Math., 37:539-560, 1979.
	15	Samir Khuller , Yoram J. Sussmann, The Capacitated K-Center Problem (Extended Abstract), Proceedings of the Fourth Annual European Symposium on Algorithms, p.152-166, September 25-27, 1996
	16	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
	17	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]
	18	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]
	19	David B. Shmoys , Éva Tardos, An approximation algorithm for the generalized assignment problem, Mathematical Programming: Series A and B, v.62 n.3, p.461-474, Dec. 8, 1993 [doi>10.1007/BF01585178]
	20	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]
	21	M. Sviridenko. Personal communication, July, 1998.
	22	A. Tamir. An O(/m2) algorithm for the p-median and related problems on tree graphs. Oper. Res. Lett., 19:59-94, 1996.
	23	S. de Vries, M. Posner, and R. Vohra. The K- median Problem on a Tree. Working paper, Ohio State University, Oct. 1998.
	24	J. Ward, R. T. Wong, P. Lemke, and A. Oudjit. Properties of the tree K-median linear programming relaxation. Unpublished manuscript, 1994.

CITED BY 55

	Ravindran Kannan , Santosh Vempala, Spectral Algorithms, Foundations and Trends® in Theoretical Computer Science, v.4 n.3–4, p.157-288, March 2009
	Samir Khuller, Algorithms column, ACM SIGACT News, v.32 n.2, June 2001
	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
	Moses Charikar , Rina Panigrahy, Clustering to minimize the sum of cluster diameters, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.1-10, July 2001, Hersonissos, Greece
	Yoonheui Kim , Victor Lesser , Deepak Ganesan , Ramesh Sitaraman, Cluster-Swap: A Distributed K-median Algorithm for Sensor Networks, Proceedings of the 2009 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology, p.363-370, September 15-18, 2009
	Ivan D. Baev , Rajmohan Rajaraman, Approximation algorithms for data placement in arbitrary networks, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.661-670, January 07-09, 2001, Washington, D.C., United States
	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
	Vijay Arya , Naveen Garg , Rohit Khandekar , Kamesh Munagala , Vinayaka Pandit, Local search heuristic for k-median and facility location problems, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.21-29, July 2001, Hersonissos, Greece
	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
	Arun Venkataramani , Phoebe Weidmann , Mike Dahlin, Bandwidth constrained placement in a WAN, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.134-143, August 2001, Newport, Rhode Island, United States
	Sudipto Guha , Adam Meyerson , Kamesh Munagala, Improved algorithms for fault tolerant facility location, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.636-641, January 07-09, 2001, Washington, D.C., United States
	Kamal Jain , Mohammad Mahdian , Amin Saberi, A new greedy approach for facility location problems, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Nina Mishra , Dan Oblinger , Leonard Pitt, Sublinear time approximate clustering, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.439-447, January 07-09, 2001, Washington, D.C., 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
	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
	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 , 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
	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
	Neal E. Young, K-medians, facility location, and the Chernoff-Wald bound, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.86-95, January 09-11, 2000, San Francisco, California, United States
	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
	Pankaj K. Agarwal , Cecilia M. Procopiuc, Approximation algorithms for projective clustering, Journal of Algorithms, v.46 n.2, p.115-139, February 2003
	Qing Zhang , Xuemin Lin, Clustering moving objects for spatio-temporal selectivity estimation, Proceedings of the fifteenth Australasian database conference, p.123-130, January 01, 2004, Dunedin, New Zealand
	Craig W. Cameron , Steven H. Low , David X. Wei, High-density model for server allocation and placement, ACM SIGMETRICS Performance Evaluation Review, v.30 n.1, June 2002
	Kamal Jain , Mohammad Mahdian , Evangelos Markakis , Amin Saberi , Vijay V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP, Journal of the ACM (JACM), v.50 n.6, p.795-824, November 2003
	Adam Meyerson , Kamesh Munagala , Serge Plotkin, Web caching using access statistics, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.354-363, January 07-09, 2001, Washington, D.C., United States
	Adam Meyerson, Profit-earning facility location, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.30-36, July 2001, Hersonissos, Greece
	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
	Piotr Indyk, Sublinear time algorithms for metric space problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.428-434, May 01-04, 1999, Atlanta, Georgia, United States
	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
	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
	Moses Charikar , Rina Panigrahy, Clustering to minimize the sum of cluster diameters, Journal of Computer and System Sciences, v.68 n.2, p.417-441, March 2004
	Nirupama Bulusu , John Heidemann , Deborah Estrin , Tommy Tran, Self-configuring localization systems: Design and Experimental Evaluation, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.1, p.24-60, February 2004
	Ramgopal R. Mettu , C. Greg Plaxton, Optimal Time Bounds for Approximate Clustering, Machine Learning, v.56 n.1-3, p.35-60
	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
	Julia Chuzhoy , Yuval Rabani, Approximating k-median with non-uniform capacities, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	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
	Sagnik Bhattacharya , Hyung Kim , Shashi Prabh , Tarek Abdelzaher, Energy-conserving data placement and asynchronous multicast in wireless sensor networks, Proceedings of the 1st international conference on Mobile systems, applications and services, p.173-185, May 05-08, 2003, San Francisco, California
	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
	Samir Khuller, Problems column, ACM Transactions on Algorithms (TALG), v.1 n.1, p.157-159, July 2005
	Sudipto Guha , Adam Meyerson , Kamesh Munagala, A constant factor approximation algorithm for the fault-tolerant facility location problem, Journal of Algorithms, v.48 n.2, p.429-440, September 2003
	Marek Chrobak , Claire Kenyon , Neal Young, The reverse greedy algorithm for the metric k-median problem, Information Processing Letters, v.97 n.2, p.68-72, 31 January 2006
	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
	Anthony Busson , Daniel Kofman , Jean-Louis Rougier, A new service overlays dimensioning approach based on stochastic geometry, Performance Evaluation, v.64 n.1, p.76-92, January, 2007
	R. C. Chakinala , A. Kumarasubramanian , K. A. Laing , R. Manokaran , C. Pandu Rangan , R. Rajaraman, Playing push vs pull: models and algorithms for disseminating dynamic data in networks, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
	Sudipto Guha , Kamesh Munagala, Exceeding expectations and clustering uncertain data, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 29-July 01, 2009, Providence, Rhode Island, USA
	Samee Ullah Khan , Ishfaq Ahmad, Comparison and analysis of ten static heuristics-based Internet data replication techniques, Journal of Parallel and Distributed Computing, v.68 n.2, p.113-136, February, 2008
	Sanjeev Arora , Satyen Kale, A combinatorial, primal-dual approach to semidefinite programs, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Arora Sanjeev , Ravi Kannan, Learning mixtures of arbitrary gaussians, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.247-257, July 2001, Hersonissos, Greece
	Liansheng Tan , Li Jin , Yi Pan, Efficient placement of proxies for hierarchical reliable multicast, Computer Communications, v.31 n.9, p.1842-1855, June, 2008
	Sudipto Guha , Kamesh Munagala, Model-driven optimization using adaptive probes, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.308-317, January 07-09, 2007, New Orleans, Louisiana
	Maria-Florina Balcan , Avrim Blum , Santosh Vempala, A discriminative framework for clustering via similarity functions, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	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
	Ming Hua , Jian Pei , Ada W. Fu , Xuemin Lin , Ho-Fung Leung, Top-k typicality queries and efficient query answering methods on large databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.18 n.3, p.809-835, June 2009
	R. Ravi , Amitabh Sinha, Approximation Algorithms for Problems Combining Facility Location and Network Design, Operations Research, v.54 n.1, p.73-81, January-February 2006