Abstract
We study geometric versions of the min-size k -clustering problem, a clustering problem which generalizes clustering to minimize the sum of cluster radii and has important applications. We prove that the problem can be solved in polynomial time when the points to be clustered are located on a line. For Euclidean spaces of higher dimensions, we show that the problem is NP-hard and present polynomial time approximation schemes. The latter result yields an improved approximation algorithm for the related problem of k-clustering to minimize the sum of cluster diameters.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arora, S., Raghavan, P., Rao, S.: Approximation schemes for the Euclidean k-medians and related problems. In: Proc. of the 30th ACM Symposium on Theory of Computing (STOC 1998), pp. 106–113 (1998)
Bǎdoiu, M., Har-Peled, S., Indyk, P.: Approximate clustering via core-sets. In: Proc. of the 34th Annual ACM Symposium on Theory of Computing (STOC 2002), pp. 250–257 (2002)
Bartal, Y., Charikar, M., Raz, D.: Approximating min-sum k-clustering in metric spaces. In: Proc. of the 33rd Annual ACM Symposium on Theory of computing (STOC 2001), pp.11–20 (2001)
Brucker, P.: On the complexity of clustering problems. Optimization and Operations Research, Lecture Notes in Economics and Mathematical Sciences 157, 45–54 (1978)
Charikar, M., Guha, S., Tardos, E., Shmoys, D.S.: A constant factor approximation algorithm for the k-median problem. Journal of Computer and Systems Sciences 65(1), 129–149 (2002)
Charikar, M., Panigrahy, R.: Clustering to minimize the sum of cluster diameters. Journal of Computer and Systems Sciences 68(2), 417–441 (2004)
Capoyleas, V., Rote, G., Woeginger, G.J.: Geometric Clusterings. Journal of Algorithms 12(2), 341–356 (1991)
Doddi, S.R., Marathe, M.V., Ravi, S.S., Taylor, D.S., Widmayer, P.: Approximation algorithms for clustering to minimize the sum of diameters. Nordic Journal of Computing 7(3), 185–203 (2000)
Erlebach, T., Jansen, K., Seidel, E.: Polynomial-time approximation schemes for geometric graphs. In: Proc. of the 12th Annual Symposium on Discrete Algorithms (SODA 2001), pp. 671–679 (2001)
de la Vega, W.F., Karpinski, M., Kenyon, C., Rabani, Y.: Approximation schemes for clustering problems. In: Proc. of the 35th Annual ACM Symposium on Theory of Computing (STOC 2003), pp. 50–58 (2003)
Freund, A., Rawitz, D.: Combinatorial interpretations of dual fitting and primal fitting. In: Solis-Oba, R., Jansen, K. (eds.) WAOA 2003. LNCS, vol. 2909, pp. 137–150. Springer, Heidelberg (2004)
Hansen, P., Jaumard, B.: Minimum sum of diameters clustering. Journal of Classification 4, 215–226 (1987)
Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and k-median problems using the primal-dual scheme and Lagrangian relaxation. Journal of the ACM 48, 274–296 (2001)
Lev-Tov, N., Peleg, D.: Polynomial time approximation schemes for base station coverage with minimum total radii. Computer Networks 47, 489–501 (2005)
Monma, C.L., Suri, S.: Partitioning points and graphs to minimize the maximum or the sum of diameters. In: Graph Theory, Combinatorics and Applications, pp. 880–912. John Wiley and Sons, Chichester (1991)
Ostrovsky, R., Rabani, Y.: Polynomial-time approximation schemes for geometric clustering problems. Journal of the ACM 49(2), 139–156 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bilò, V., Caragiannis, I., Kaklamanis, C., Kanellopoulos, P. (2005). Geometric Clustering to Minimize the Sum of Cluster Sizes. In: Brodal, G.S., Leonardi, S. (eds) Algorithms – ESA 2005. ESA 2005. Lecture Notes in Computer Science, vol 3669. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11561071_42
Download citation
DOI: https://doi.org/10.1007/11561071_42
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29118-3
Online ISBN: 978-3-540-31951-1
eBook Packages: Computer ScienceComputer Science (R0)