Approximating min-sum k-clustering in metric spaces

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximating min-sum k-clustering in metric spaces

Full text

Pdf (256 KB)

Source

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

Hersonissos, Greece

Pages: 11 - 20

Year of Publication: 2001

ISBN:1-58113-349-9

Authors

Yair Bartal	Computer Science Dept., Hebrew University, Israel and Bell Labs, Lucent Technologies
Moses Charikar	Google, Inc., Mountain View, CA and Computer Science Dept., Stanford University
Danny Raz	Computer Science Dept., Technion, Israel and Bell Labs, Lucent Technologies

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): 53, Citation Count: 18

Additional Information:

abstract 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/380752.380754 What is a DOI?

ABSTRACT

The min-sum k-clustering problem in a metric space is to find a partition of the space into k clusters as to minimize the total sum of distances between pairs of points assigned to the same cluster. We give the first polynomial time non-trivial approximation algorithm for this problem. The algorithm provides an $\ratio$ approximation to the min-sum k-clustering problem in general metric spaces, with running time $\runtime$. The result is based on embedding of metric spaces into hierarchically separated trees. We also provide a bicriteria approximation result that provides a constant approximation factor solution with only a constant factor increase in the number of clusters. This result is obtained by modifying and drawing ideas from recently developed primal dual approximation algorithms for facility location.

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	Moses Charikar , Chandra Chekuri , Ashish Goel , Sudipto Guha , Serge Plotkin, Approximating a Finite Metric by a Small Number of Tree Metrics, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.379, November 08-11, 1998
	4	Nili Guttmann-Beck , Refael Hassin, Approximation algorithms for min-sum p-clustering, Discrete Applied Mathematics, v.89 n.1-3, p.125-142, Dec. 1998 [doi>10.1016/S0166-218X(98)00100-0]
	5	Piotr Indyk, A Sublinear Time Approximation Scheme for Clustering in Metric Spaces, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.154, October 17-18, 1999
	6	Kamal Jain , Vijay V. Vazirani, Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.2, October 17-18, 1999
	7	V. Kann, S. Khanna, J. Lagergren, and A. Panconesi. On the hardness of max k-cut and its dual. In Israeli Symposium on Theoretical Computer Science, pages 61-67, 1996.
	8	Madhav V. Marathe , R. Ravi , Ravi Sundaram , S. S. Ravi , Daniel J. Rosenkrantz , Harry B. Hunt, III, Bicriteria network design problems, Journal of Algorithms, v.28 n.1, p.142-171, July 1, 1998 [doi>10.1006/jagm.1998.0930]
	9	Sartaj Sahni , Teofilo Gonzalez, P-Complete Approximation Problems, Journal of the ACM (JACM), v.23 n.3, p.555-565, July 1976 [doi>10.1145/321958.321975]
	10	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 [doi>10.1145/335305.335373]

CITED BY 18

	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
	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
	Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	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
	Sudipto Guha , Kamesh Munagala, Generalized clustering, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.484-485, January 06-08, 2002, San Francisco, California
	David B. Shmoys , Chaitanya Swamy , Retsef Levi, Facility location with Service Installation Costs, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Yair Bartal , Manor Mendel, Randomized k-server algorithms for growth-rate bounded graphs, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	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
	Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Journal of Computer and System Sciences, v.69 n.3, p.485-497, November 2004
	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
	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
	Yair Bartal , Manor Mendel, Randomized k-server algorithms for growth-rate bounded graphs, Journal of Algorithms, v.55 n.2, p.192-202, May 2005
	Chandra Chekuri , Guy Even , Guy Kortsarz, A greedy approximation algorithm for the group Steiner problem, Discrete Applied Mathematics, v.154 n.1, p.15-34, 1 January 2006
	Rong Ge , Martin Ester , Byron J. Gao , Zengjian Hu , Binay Bhattacharya , Boaz Ben-Moshe, Joint cluster analysis of attribute data and relationship data: The connected k-center problem, algorithms and applications, ACM Transactions on Knowledge Discovery from Data (TKDD), v.2 n.2, p.1-35, July 2008
	Ittai Abraham , Yair Bartal , Ofer Neimany, Advances in metric embedding theory, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Ureil Feige , Nicole Immorlica , Vahab Mirrokni , Hamid Nazerzadeh, A combinatorial allocation mechanism with penalties for banner advertising, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China
	Ke Chen, A constant factor approximation algorithm for k-median clustering with outliers, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.826-835, January 20-22, 2008, San Francisco, California
	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