Approximation schemes for clustering problems

ABSTRACT

Let k be a fixed integer. We consider the problem of partitioning an input set of points endowed with a distance function into k clusters. We give polynomial time approximation schemes for the following three clustering problems: Metric k-Clustering, l ²₂ k-Clustering, and l²₂ k-Median. In the k-Clustering problem, the objective is to minimize the sum of all intra-cluster distances. In the k-Median problem, the goal is to minimize the sum of distances from points in a cluster to the (best choice of) cluster center. In metric instances, the input distance function is a metric. In l ²₂ instances, the points are in R ^d and the distance between two points x,y is measured by x−y ²₂ (notice that (R ^d, ⋅ ²₂ is not a metric space). For the first two problems, our results are the first polynomial time approximation schemes. For the third problem, the running time of our algorithms is a vast improvement over previous work.

REFERENCES

• 1: 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
• 2: N. Alon , S. Dar , M. Parnas , D. Ron, Testing of clustering, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.240, November 12-14, 2000
• 3: Noga Alon , Benny Sudakov, On two segmentation problems, Journal of Algorithms, v.33 n.1, p.173-184, Oct. 1999 [doi>10.1006/jagm.1999.1024]
• 4: Sanjeev Arora , David Karger , Marek Karpinski, Polynomial time approximation schemes for dense instances of NP -hard problems, Journal of Computer and System Sciences, v.58 n.1, p.193-210, Feb. 1999 [doi>10.1006/jcss.1998.1605]
• 5: 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]
• 6: 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 [doi>10.1145/509907.509947]
• 7: Yair Bartal , Moses Charikar , Danny Raz, Approximating min-sum k-clustering in metric spaces, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.11-20, July 2001, Hersonissos, Greece [doi>10.1145/380752.380754]
• 8: Andrei Z. Broder , Steven C. Glassman , Mark S. Manasse , Geoffrey Zweig, Syntactic clustering of the Web, Selected papers from the sixth international conference on World Wide Web, p.1157-1166, September 1997, Santa Clara, California, United States
• 9: B. Carl and I. Stephani. Entropy, Compactness and the Approximation of Operators. Cambridge University Press, 1990.
• 10: Moses Charikar , Sudipto Guha, Improved Combinatorial Algorithms for the Facility Location and k-Median Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.378, October 17-18, 1999
• 11: 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]
• 12: S. Deerwester, S. T. Dumais, T. K. Landauer, G. W. Furnas, and R. A. Harshman. Indexing by latent semantic analysis. Journal of the Society for Information Science, 41(6):391--407, 1990.
• 13: Vega W. Fernandez de la , Karpinski Marek , Kenyon Claire, A Polynomial Time Approximation Scheme for Metric MIN-BISECTION, University of Bonn, 2002
• 14: W. Fernandez de la Vega , Claire Kenyon, A Randomized Approximation Scheme for Metric MAX-CUT, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.468, November 08-11, 1998
• 15: 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
• 16: C. Faloutsos , R. Barber , M. Flickner , J. Hafner , W. Niblack , D. Petkovic , W. Equitz, Efficient and effective querying by image content, Journal of Intelligent Information Systems, v.3 n.3-4, p.231-262, July 1994 [doi>10.1007/BF00962238]
• 17: Naveen Garg , Vijay V. Vazirani , Mihalis Yannakakis, Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications, SIAM Journal on Computing, v.25 n.2, p.235-251, February 1996 [doi>10.1137/S0097539793243016]
• 18: Oded Goldreich , Shari Goldwasser , Dana Ron, Property testing and its connection to learning and approximation, Journal of the ACM (JACM), v.45 n.4, p.653-750, July 1998 [doi>10.1145/285055.285060]
• 19: 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
• 20: 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]
• 21: 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
• 22: 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
• 23: V. Kann, S. Khanna, J. Lagergren, and A. Panconesi. On the hardness of approximating Max k-Cut and its dual. In Proc. of the 4th Israeli Symp. on Theory of Computing and Systems (ISTCS), 1996. Also in Chicago Journal of Theoretical Computer Science, 1997.
• 24: 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 [doi>10.1145/276698.276860]
• 25: 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
• 26: 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 [doi>10.1145/506147.506149]
• 27: 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]
• 28: 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]
• 29: R. Shamir and R. Sharan. Algorithmic approaches to clustering gene expression data. In T. Jiang, T. Smith, Y. Xu, M.Q. Zhang eds., Current Topics in Computational Biology, MIT Press, to appear.
• 30: Michael J. Swain , Dana H. Ballard, Color indexing, International Journal of Computer Vision, v.7 n.1, p.11-32, Nov. 1991 [doi>10.1007/BF00130487]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory