Optimal algorithms for approximate clustering

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimal algorithms for approximate clustering

Full text

Pdf (1.08 MB)

Source

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

Chicago, Illinois, United States

Pages: 434 - 444

Year of Publication: 1988

ISBN:0-89791-264-0

Authors

Tomás Feder	Computer Science Department, Stanford University, Stanford, CA
Daniel Greene	Xerox Palo Alto Research Center, Palo Alto, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 24, Downloads (12 Months): 166, Citation Count: 54

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

ABSTRACT

In a clustering problem, the aim is to partition a given set of n points in d-dimensional space into k groups, called clusters, so that points within each cluster are near each other. Two objective functions frequently used to measure the performance of a clustering algorithm are, for any L4 metric, (a) the maximum distance between pairs of points in the same cluster, and (b) the maximum distance between points in each cluster and a chosen cluster center; we refer to either measure as the cluster size. We show that one cannot approximate the optimal cluster size for a fixed number of clusters within a factor close to 2 in polynomial time, for two or more dimensions, unless P=NP. We also present an algorithm that achieves this factor of 2 in time &Ogr;(n log k), and show that this running time is optimal in the algebraic decision tree model. For a fixed cluster size, on the other hand, we give a polynomial time approximation scheme that estimates the optimal number of clusters under the second measure of cluster size within factors arbitrarily close to 1. Our approach is extended to provide approximation algorithms for the restricted centers, suppliers, and weighted suppliers problems that run in optimal &Ogr;(n log k) time and achieve optimal or nearly optimal approximation bounds.

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.

	Ba83	Brenda S. Baker, "Approximation algorithms for NP-complete problems on planar graphs." Proc. 24th IEEE FOCS (1983), pp. 265 273.
	Be83	Michael Ben-Or, Lower bounds for algebraic computation trees, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.80-86, December 1983 [doi>10.1145/800061.808735]
	Br77	P. Bruckcr, "On the complexity of clustering problems," in Optimization and Operations Research (R. Hcnn, B. Kortc, W. Olctti eds.), Springer-Verlag, Berlin, Heidelberg, New York (1977), pp. 45-54.
	Eq87	William Equitz, "Fast algorithms for vector quantization picture coding," Proc. International Conference on Acoustics, Speech, an(t Signal Processing (1987), I)P- 725 728.
	FPT81	R.J. Fowler, M.S. Paterson and S.L. Tanimoto, "Optimal packing and covering in the plane are NP-complete," Inf. Proc. Letters, Vol. 12, No. 3 (1981), pp. 133 137.
	GJ77	M.R. Garey and D.S. Johnson, "The rectilinear Steiner tree problem is NP- complete," Siam J. Appl. Math. 32 (1977), pp. 826-834.
	GJ79	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	Go85	Te6filo F. Gonz~ez, "Clustering to minimize the maximum interclustcr distance," Theoretical Computer Science 38, North- Holland (1985), pp. 293 306.
	Gr84	Robert M. Gray, "Vector quantization," IEEE ASSP Magazim:, April (1984), pp. 4-29.
	HS85	D.S. Hochbaum and D.B. Shmoys, "A best possible heuristic for the k-center problem," Mathematics of Operations Research, Vol. 10, No. 2 (1985), the. 180 184.
	HS86	Dorit S. Hochbaum , David B. Shmoys, A unified approach to approximation algorithms for bottleneck problems, Journal of the ACM (JACM), v.33 n.3, p.533-550, July 1986 [doi>10.1145/5925.5933]
	HN79	W.L. Hsu and G.L. Nemhauser, "Easy and hard bottleneck location problems," Discr. Appl. Math. 1 (1979), pp. 209 215.
	MS84	N. Megiddo and K.J. Supowit, "On the complexity of some common geometric location problems," Siam J. Comput., Vol. 13, No. 1 (1984), pp. 182 196.
	Me88	Stuart G. Mentzer, "Lower bounds on metric k-center problems," Manuscript, 1988.
	PS85	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	Va86	Pravin M. Vaidya, "An optimal algorithm for the all-nearest-neighbors problent," Proc. 27th IEEE FOCS (1986), pp. 117 122.
	Vs87	Stephen Vavasis, personal communication.

CITED BY 54

	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
	Yiming Yang , Tom Pierce , Jaime Carbonell, A study of retrospective and on-line event detection, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.28-36, August 24-28, 1998, Melbourne, Australia
	Pankaj K. Agarwal , Cecilia M. Procopiuc, Exact and approximation algorithms for clustering, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.658-667, January 25-27, 1998, San Francisco, California, United States
	Moses Charikar , Chandra Chekuri , Tomás Feder , Rajeev Motwani, Incremental clustering and dynamic information retrieval, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.626-635, May 04-06, 1997, El Paso, Texas, United States
	Javed Aslam , Katya Pelekhov , Daniela Rus, A practical clustering algorithm for static and dynamic information organization, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.51-60, January 17-19, 1999, Baltimore, Maryland, United States
	C. J. Alpert , A. B. Kahng, Geometric embeddings for faster and better multi-way netlist partitioning, Proceedings of the 30th international conference on Design automation, p.743-748, June 14-18, 1993, Dallas, Texas, 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
	Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Y. Wu, An optimal algorithm for approximate nearest neighbor searching fixed dimensions, Journal of the ACM (JACM), v.45 n.6, p.891-923, Nov. 1998
	Pankaj K. Agarwal , Micha Sharir, Planar geometric location problems and maintaining the width of a planar set, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.449-458, January 28-30, 1991, San Francisco, California, United States
	Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Wu, An optimal algorithm for approximate nearest neighbor searching, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.573-582, January 23-25, 1994, Arlington, Virginia, United States
	Hai Huang , Andréa W. Richa , Michael Segal, Approximation algorithms for the mobile piercing set problem with applications to clustering in ad-hoc networks, Proceedings of the 6th international workshop on Discrete algorithms and methods for mobile computing and communications, September 28-28, 2002, Atlanta, Georgia, USA
	Marek Chrobak , David Eppstein , Giuseppe F. Italiano , Moti Yung, Efficient sequential and parallel algorithms for computing recovery points in trees and paths, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.158-167, January 28-30, 1991, San Francisco, California, United States
	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
	Mary Inaba , Naoki Katoh , Hiroshi Imai, Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering: (extended abstract), Proceedings of the tenth annual symposium on Computational geometry, p.332-339, June 06-08, 1994, Stony Brook, New York, United States
	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
	Domenico Cantone , Alfredo Ferro , Alfredo Pulvirenti , Diego Reforgiato Recupero , Dennis Shasha, Antipole Tree Indexing to Support Range Search and K-Nearest Neighbor Search in Metric Spaces, IEEE Transactions on Knowledge and Data Engineering, v.17 n.4, p.535-550, April 2005
	Jon Kleinberg , Christos Papadimitriou , Prabhakar Raghavan, Segmentation problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.473-482, May 24-26, 1998, Dallas, Texas, 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
	Magnús M. Halldórsson , Kazuo Iwano , Naoki Katoh , Takeshi Tokuyama, Finding subsets maximizing minimum structures, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.150-159, January 22-24, 1995, San Francisco, California, United States
	Franz Aurenhammer , Naoki Katoh , Hiromichi Kojima , Makoto Ohsaki , Yinfeng Xu, Approximating uniform triangular meshes in polygons, Theoretical Computer Science, v.289 n.2, p.879-895, 30 October 2002
	Michael Hoffmann, A simple linear algorithm for computing rectilinear 3-centers, Computational Geometry: Theory and Applications, v.31 n.3, p.150-165, June 2005
	Pankaj K. Agarwal , Cecilia M. Procopiuc, Approximation algorithms for projective clustering, Journal of Algorithms, v.46 n.2, p.115-139, February 2003
	Armin Iske, Progressive scattered data filtering, Journal of Computational and Applied Mathematics, v.158 n.2, p.297-316, 15 September 2003
	Ralf Herbrich , Robert C. Williamson, Algorithmic luckiness, The Journal of Machine Learning Research, 3, p.175-212, 3/1/2003
	Sameer Agarwal , Ravi Ramamoorthi , Serge Belongie , Henrik Wann Jensen, Structured importance sampling of environment maps, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
	Nina Mishra , Dana Ron , Ram Swaminathan, A New Conceptual Clustering Framework, Machine Learning, v.56 n.1-3, p.115-151
	Javed Aslam , Katya Pelekhov , Daniela Rus, Static and dynamic information organization with star clusters, Proceedings of the seventh international conference on Information and knowledge management, p.208-217, November 02-07, 1998, Bethesda, Maryland, United States
	Jukka Suomela, Approximating relay placement in sensor networks, Proceedings of the 3rd ACM international workshop on Performance evaluation of wireless ad hoc, sensor and ubiquitous networks, October 06-06, 2006, Terromolinos, Spain
	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
	Jie Gao , Leonidas J. Guibas , An Nguyen, Deformable spanners and applications, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, 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
	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
	Srinivas Doddi , Madhav V. Marathe , S. S. Ravi , David Scot Taylor , Peter Widmayer, Approximation algorithms for clustering to minimize the sum of diameters, Nordic Journal of Computing, v.7 n.3, p.185-203, Fall 2000
	Hai Huang , Andréa W. Richa , Michael Segal, Approximation algorithms for the mobile piercing set problem with applications to clustering in ad-hoc networks, Mobile Networks and Applications, v.9 n.2, p.151-161, April 2004
	Sanjoy Dasgupta , Philip M. Long, Performance guarantees for hierarchical clustering, Journal of Computer and System Sciences, v.70 n.4, p.555-569, June 2005
	Sariel Har-Peled , Manor Mendel, Fast construction of nets in low dimensional metrics, and their applications, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	Jon Kleinberg , Christos Papadimitriou , Prabhakar Raghavan, Segmentation problems, Journal of the ACM (JACM), v.51 n.2, p.263-280, March 2004
	Taneli Mielikäinen, Frequency-based views to pattern collections, Discrete Applied Mathematics, v.154 n.7, p.1113-1139, 1 May 2006
	Jie Gao , Leonidas J. Guibas , An Nguyen, Deformable spanners and applications, Computational Geometry: Theory and Applications, v.35 n.1, p.2-19, August 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
	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
	Filippo Geraci , Marco Pellegrini , Paolo Pisati , Fabrizio Sebastiani, A scalable algorithm for high-quality clustering of web snippets, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France
	Kai Zhang , James T. Kwok, Block-quantized kernel matrix for fast spectral embedding, Proceedings of the 23rd international conference on Machine learning, p.1097-1104, June 25-29, 2006, Pittsburgh, Pennsylvania
	Jiyuan An , Jeffrey Xu Yu , Chotirat Ann Ratanamahatana , Yi-Ping Phoebe Chen, A dimensionality reduction algorithm and its application for interactive visualization, Journal of Visual Languages and Computing, v.18 n.1, p.48-70, February, 2007
	David Eppstein, Squarepants in a tree: sum of subtree clustering and hyperbolic pants decomposition, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.29-38, January 07-09, 2007, New Orleans, Louisiana
	Marco Furini , Filippo Geraci , Manuela Montangero , Marco Pellegrini, VISTO: visual storyboard for web video browsing, Proceedings of the 6th ACM international conference on Image and video retrieval, p.635-642, July 09-11, 2007, Amsterdam, The Netherlands
	Kai Zhang , James T. Kwok, Density-weighted nyström method for computing large kernel eigensystems, Neural Computation, v.21 n.1, p.121-146, Jan. 2009
	Flavio Chierichetti , Ravi Kumar , Sergei Vassilvitskii, Similarity caching, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 29-July 01, 2009, Providence, Rhode Island, USA
	Pankaj K. Agarwal , Esther Ezra , Micha Shair, Near-linear approximation algorithms for geometric hitting sets, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark
	Boris Aronov , Esther Ezra , Micha Shair, Small-size ε-nets for axis-parallel rectangles and boxes, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	David Eppstein, Squarepants in a tree: Sum of subtree clustering and hyperbolic pants decomposition, ACM Transactions on Algorithms (TALG), v.5 n.3, p.1-24, July 2009
	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
	Chandra Chekuri , Kenneth L. Clarkson , Sariel Har-Peled, On the set multi-cover problem in geometric settings, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark
	Guang Xu , Jinhui Xu, Efficient approximation algorithms for clustering point-sets, Computational Geometry: Theory and Applications, v.43 n.1, p.59-66, January, 2010