Clustering to minimize the sum of cluster diameters

ABSTRACT

We study the problem of clustering points in a metric space so as to minimize the sum of cluster diameters. Significantly improving on previous results, we present a primal-dual based constant factor approximation algorithm for this problem. We present a simple greedy algorithm that achieves a logarithmic approximation which also applies when the distance function is asymmetric. The previous best known result obtained a logarithmic approximation with a constant factor blowup in the number of clusters. We also obtain an incremental clustering algorithm that maintains a solution whose cost is at most a constant factor times that of optimal with a constant factor blowup in the number of clusters.

REFERENCES

• 1: 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]
• 2: 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 [doi>10.1145/258533.258657]
• 3: 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
• 4: 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]
• 5: 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
• 6: 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
• 7: G. Cornejols, G. L. Nemhauser, and L. A. Wolsey. Discrete Location Theory, chapter The uncapacitated facility location problem. John Wiley and Sons, Inc., New York, 1990.
• 8: Srinivas Doddi , Madhav V. Marathe , S. S. Ravi , David Scot Taylor , Peter Widmayer, Approximation Algorithms for Clustering to Minimize the Sum of Diameters, Proceedings of the 7th Scandinavian Workshop on Algorithm Theory, p.237-250, July 05-07, 2000
• 9: M. Dyer and A. M. Frieze. A simple heuristic for the p-center problem. Operations Research Letters, 3:285-288, 1985.
• 10: 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
• 11: 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]
• 12: Pierre Hansen , Brigitte Jaumard, Cluster analysis and mathematical programming, Mathematical Programming: Series A and B, v.79 n.1-3, p.191-215, Oct. 1, 1997 [doi>10.1007/BF02614317]
• 13: D. S. Hochbaum and D. B. Shmoys. A best possible approximation algorithm for the k-center problem. Mathematics of Operations Research, 10:180-184, 1985.
• 14: 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
• 15: O. Kariv and S. L. Hakimi. An algorithmic approach to network location problems, part ii: p-medians. SIAM Journal of Applied Mathematics, 37:539-560, 1979.
• 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: C. L. Monma and S. Suri. Partitioning points and graphs to minimize the maximum or the sum of diameters. Graph Theory, Combinatorics and Applications, pages 880-912, 1991.
• 19: 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]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

General Terms:
Algorithms, Design, Measurement, Performance, Theory, Verification