research-article

On clustering to minimize the sum of radii

Authors:

Kasturi VaradarajanAuthors Info & Claims

SODA '08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 819 - 825

Published: 20 January 2008 Publication History

Get Access

Abstract

Given a metric d defined on a set V of points (a metric space), we define the ball B(v, r) centered at u ∈ V and having radius r ≥ 0 to be the set {q ∈ V/d(v, q) ≤r}. In this work, we consider the problem of computing a minimum cost k-cover for a given set P ⊆ V of n points, where k > 0 is some given integer which is also part of the input. For k ≥ 0, a k-cover for subset Q ⊆ P is a set of at most k balls, each centered at a point in P, whose union covers (contains) Q. The cost of a set D of balls, denoted cost(D), is the sum of the radii of those balls.

References

[1]

S. Arora. Polynomial-time approximation schemes for Euclidean TSP and other geometric problems. Proceedings of the IEEE Symposium on Foundations of Computer Science, 1996, 2--12.

Digital Library

Google Scholar

[2]

H. Alt, E. Arkin, H. Bronnimann, J. Erickson, S. Fekete, C. Knauer, J. Lenchner, J. Mitchell, and K. Whittlesey. Mininum-cost coverage of points by disks. Proceedings of the Annual Symposium on Computational Geometry, 2006, 449--458.

Digital Library

Google Scholar

[3]

Y. Bartal. Probabilistic approximations of metric spaces and its algorithmic applications. Proceedings of the IEEE Symposium on the Foundations of Computer Science, 1996, 184--193.

Digital Library

Google Scholar

[4]

M. Bern and D. Eppstein. Approximation algorithms for geometric problems. In D. Hochbaum (Ed.), Approximation algorithms for NP-hard problems, PWS Publishing Company, 1997, pages 296--345.

Digital Library

Google Scholar

[5]

V. Bilo, I. Caragiannis, C. Kaklamanis, and P. Kanellopoulos. Geometric clustering to minimize the sum of cluster sizes. Proceedings of the European Symposium on Algorithms, LNCS vol 3669, 460--471, 2005.

Digital Library

Google Scholar

[6]

M. Charikar and R. Panigrahy. Clustering to minimize the sum of cluster diameters. Journal of Computer and Systems Sciences, vol. 68 (2), 417--441, 2004.

Digital Library

Google Scholar

[7]

E. D. Demaine, J. S. B. Mitchell, and J. O'Rourke. The open problems project, Problem 33: Sum of square roots, http://maven.smith.edu/~orourke/TOPP/P33.html.

Google Scholar

[8]

S. R. Doddi, M. V. Marathe, S. S. Ravi, D. S. Taylor, and P. Widmayer. Approximation algorithms for clustering to minimize the sum of diameters. Nordic Journal of Computing, Vol 7(3), 185--203, 2000.

Digital Library

Google Scholar

[9]

J. Fakcharoenphol, S. Rao, and K. Talwar. A tight bound on approximating arbitrary metrics by tree metrics, Proceedings of the ACM Symposium on the Theory of Computing, 2003, 448--455.

Digital Library

Google Scholar

[10]

M. Gibson, G. Kanade, E. Krohn, I. Pirwani, and K. Varadarajan. On metric clustering to minimize the sum of radii. Manuscript, 2007.

Digital Library

Google Scholar

[11]

N. Lev-Tov and D. Peleg. Polynomial time approximation schems for base station coverage with minimum total radii. Computer Networks 47 (2005) 489--501.

Digital Library

Google Scholar

[12]

J. S. B. Mitchell. Guillotine subdivisions aprpoximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM Journal on Computing, 28(4): 1298--1309.

Digital Library

Google Scholar

[13]

J. Qian and C. A. Wang. How much precision is needed to compare two sums of square roots of integers?, Information Processing Letters 100 (2006): 194--198.

Digital Library

Google Scholar

Cited By

View all

Huang ZFeng QWang JXu JMarx D(2021)PTAS for minimum cost multi-covering with disksProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458117(840-859)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458117
Cohen-Addad Vde Mesmay ARotenberg ERoytman ACzumaj A(2018)The bane of low-dimensionality clusteringProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175300(441-456)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175300
Ammari H(2013)Joint k-coverage and data gathering in sparsely deployed sensor networks -- Impact of purposeful mobility and heterogeneityACM Transactions on Sensor Networks10.1145/252997810:1(1-33)Online publication date: 6-Dec-2013
https://dl.acm.org/doi/10.1145/2529978
Show More Cited By

Index Terms

On clustering to minimize the sum of radii

Recommendations

On minimum sum of radii and diameters clustering
SWAT'12: Proceedings of the 13th Scandinavian conference on Algorithm Theory

Given a metric (V,d) and an integer k, we consider the problem of covering the points of V with at most k clusters so as to minimize the sum of radii or the sum of diameters of these clusters. The former problem is called the Minimum Sum Radii (MSR) ...
On Metric Clustering to Minimize the Sum of Radii

Given an n-point metric (P,d) and an integer k>0, we consider the problem of covering P by k balls so as to minimize the sum of the radii of the balls. We present a randomized algorithm that runs in nO(logźnźlogźΔ) time and returns with high probability ...
On Minimum Sum of Radii and Diameters Clustering

Given a metric $$(V,d)$$(V,d) and an integer $$k$$k, we consider the problem of partitioning the points of $$V$$V into at most $$k$$k clusters so as to minimize the sum of radii or the sum of diameters of these clusters. The former problem is called the ...

Comments

Information & Contributors

Information

Published In

SODA '08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms

January 2008

1289 pages

Program Chair:
Shang-Hua Teng
Boston University and Akamai Technologies, Inc.

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 20 January 2008

Check for updates

Qualifiers

Research-article

Conference

SODA08

Sponsor:

SIGACT

SODA08: 19th ACM-SIAM Symposium on Discrete Algorithms

January 20 - 22, 2008

California, San Francisco

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
309
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Huang ZFeng QWang JXu JMarx D(2021)PTAS for minimum cost multi-covering with disksProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458117(840-859)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458117
Cohen-Addad Vde Mesmay ARotenberg ERoytman ACzumaj A(2018)The bane of low-dimensionality clusteringProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175300(441-456)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175300
Ammari H(2013)Joint k-coverage and data gathering in sparsely deployed sensor networks -- Impact of purposeful mobility and heterogeneityACM Transactions on Sensor Networks10.1145/252997810:1(1-33)Online publication date: 6-Dec-2013
https://dl.acm.org/doi/10.1145/2529978
Fotakis DKoutris P(2012)Online sum-radii clusteringProceedings of the 37th international conference on Mathematical Foundations of Computer Science10.1007/978-3-642-32589-2_36(395-406)Online publication date: 27-Aug-2012
https://dl.acm.org/doi/10.1007/978-3-642-32589-2_36
Chambers EFekete SHoffmann HMarinakis DMitchell JSrinivasan VStege UWhitesides S(2011)Connecting a set of circles with minimum sum of radiiProceedings of the 12th international conference on Algorithms and data structures10.5555/2033190.2033206(183-194)Online publication date: 15-Aug-2011
https://dl.acm.org/doi/10.5555/2033190.2033206
Garg SKanade G(2011)Topology construction for rural wireless mesh networks - a geometric approachProceedings of the 2011 international conference on Computational science and its applications - Volume Part III10.5555/2029312.2029321(107-120)Online publication date: 20-Jun-2011
https://dl.acm.org/doi/10.5555/2029312.2029321
Abu-Affash ACarmi PKatz MMorgenstern G(2011)Multi cover of a polygon minimizing the sum of areasProceedings of the 5th international conference on WALCOM: algorithms and computation10.5555/1966169.1966190(134-145)Online publication date: 18-Feb-2011
https://dl.acm.org/doi/10.5555/1966169.1966190
Gibson MKanade GKrohn EPirwani IVaradarajan K(2010)On Metric Clustering to Minimize the Sum of RadiiAlgorithmica10.5555/3118227.311847657:3(484-498)Online publication date: 1-Jul-2010
https://dl.acm.org/doi/10.5555/3118227.3118476
Mahajan MNimbhorkar PVaradarajan K(2009)The Planar k-Means Problem is NP-HardProceedings of the 3rd International Workshop on Algorithms and Computation10.1007/978-3-642-00202-1_24(274-285)Online publication date: 18-Feb-2009
https://dl.acm.org/doi/10.1007/978-3-642-00202-1_24
Gibson MKanade GKrohn EPirwani IVaradarajan K(2008)On Metric Clustering to Minimize the Sum of RadiiProceedings of the 11th Scandinavian workshop on Algorithm Theory10.1007/978-3-540-69903-3_26(282-293)Online publication date: 2-Jul-2008
https://dl.acm.org/doi/10.1007/978-3-540-69903-3_26

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

On minimum sum of radii and diameters clustering

On Metric Clustering to Minimize the Sum of Radii

On Minimum Sum of Radii and Diameters Clustering

Comments

Information

Published In

Sponsors

Publisher

Publication History

Check for updates

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations