C. Greg Plaxton
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.
- V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala, and V. Pandit. Local search heuristics for k-median and facility location problems. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, pages 21--29, July 2001. Google Scholar
Digital Library
- Z. Bar-Joseph, E. D. Demaine, D. K. Gifford, A. M. Hamel, T. S. Jaakkola, and N. Srebro. K-ary clustering with optimal leaf ordering for gene expression data. In R. Guigó and D. Gusfield, editors, Proceedings of the 2nd International Workshop on Algorithms in Bioinformatics, volume 2452 of Lecture Notes in Computer Science, pages 506--520. Springer, September 2002. Google ScholarDigital Library
- M. Charikar, S. Guha, É. Tardos, and D. B. Shmoys. A constant-factor approximation algorithm for the k-median problem. Journal of Computer and System Sciences, 65:129--149, 2002. Google ScholarDigital Library
- S. Dasgupta. Performance guarantees for hierarchical clustering. In J. Kivinen and R. H. Sloan, editors, Proceedings of the 15th Annual Conference on Computational Learning Theory, volume 2375 of Lecture Notes in Computer Science, pages 351--363. Springer, July 2002. Google ScholarDigital Library
- T. F. Gonzáalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293--306, 1985.Google ScholarCross Ref
- S. Guha and S. Khuller. Greedy strikes back: Improved facility location algorithms. Journal of Algorithms, 31:228--248, 1999. Google ScholarDigital Library
- D. S. Hochbaum and D. B. Shmoys. A best possible heuristic for the k-center problem. Mathematics of Operations Research, 10:180--184, 1985.Google ScholarDigital Library
- K. Jain, M. Mahdian, and A. Saberi. A new greedy approach for facility location problems. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing, pages 731--740, May 2002. Google ScholarDigital Library
- M. Mahdian, Y. Ye, and J. Zhang. Improved approximation algorithms for metric facility location problems. In K. Jansen, S. Leonardi, and V. Vazirani, editors, Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, volume 2462 of Lecture Notes in Computer Science, pages 229--242. Springer, September 2002. Google ScholarDigital Library
- R. R. Mettu and C. G. Plaxton. The online median problem. In Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, pages 339--348, November 2000. The journal version, to appear in SIAM Journal on Computing, provides details regarding the extension of the online median result to α-approximate metric spaces for any constant α. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- D. B. Shmoys, É. Tardos, and K. Aardal. Approximation algorithms for facility location problems. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages 265--274, May 1997. Google ScholarDigital Library
- M. Thorup. Quick and good facility location. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 178--185, January 2003. Google ScholarDigital Library
Index Terms
- Approximation algorithms for hierarchical location problems
Recommendations
Approximation algorithms for hierarchical location problems
Special issue on network algorithms 2005We 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 ...
Hierarchical Means Clustering
AbstractIn the cluster analysis literature, there are several partitioning (non-hierarchical) methods for clustering multivariate objects based on model estimation. Distinct to these methods is the use of a system of n nested statistical models and the ...
Hierarchical Clustering Algorithms for Document Datasets
Fast and high-quality document clustering algorithms play an important role in providing intuitive navigation and browsing mechanisms by organizing large amounts of information into a small number of meaningful clusters. In particular, clustering ...
Comments