Approximation algorithms for hierarchical location problems

ABSTRACT

We formulate and (approximately) solve hierarchical versions of two prototypical problems in discrete location theory, namely, the metric uncapacitated k-median and facility location problems. Our work yields new insights into hierarchical clustering, a widely used technique in data analysis. First, we show that every metric space admits a hierarchical clustering that is within a constant factor of optimal at every level of granularity with respect to the average (squared) distance objective. Second, we provide a natural solution to the leaf ordering problem encountered in the traditional dendrogram-based approach to the visualization of hierarchical clusterings.

REFERENCES

• 1: 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 [doi>10.1145/380752.380755]
• 2: Ziv Bar-Joseph , Erik D. Demaine , David K. Gifford , Angèle M. Hamel , Tommi Jaakkola , Nathan Srebro, K-ary Clustering with Optimal Leaf Ordering for Gene Expression Data, Proceedings of the Second International Workshop on Algorithms in Bioinformatics, p.506-520, September 17-21, 2002
• 3: Moses Charikar , Sudipto Guha , Éva Tardos , David B. Shmoys, A constant-factor approximation algorithm for the k-median problem, Journal of Computer and System Sciences, v.65 n.1, p.129-149, August 2002 [doi>10.1006/jcss.2002.1882]
• 4: Sanjoy Dasgupta, Performance Guarantees for Hierarchical Clustering, Proceedings of the 15th Annual Conference on Computational Learning Theory, p.351-363, July 08-10, 2002
• 5: T. F. Gonzáalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293--306, 1985.
• 6: Sudipto Guha , Samir Khuller, Greedy strikes back: improved facility location algorithms, Journal of Algorithms, v.31 n.1, p.228-248, April 1999 [doi>10.1006/jagm.1998.0993 ]
• 7: D. S. Hochbaum and D. B. Shmoys. A best possible heuristic for the k-center problem. Mathematics of Operations Research, 10:180--184, 1985.
• 8: 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 [doi>10.1145/509907.510012]
• 9: Mohammad Mahdian , Yinyu Ye , Jiawei Zhang, Improved Approximation Algorithms for Metric Facility Location Problems, Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, p.229-242, September 17-21, 2002
• 10: R. R. Mettu , C. G. Plaxton, The online median problem, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.339, November 12-14, 2000
• 11: R. R. Mettu and C. G. Plaxton. Optimal time bounds for approximate clustering. In Proceedings of the 18th Conference on Uncertainty in Artifical Intelligence, pages 344--351, August 2002.
• 12: 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]
• 13: Mikkel Thorup, Quick and good facility location, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Theory

Keywords:
discrete location theory, hierarchical clustering