On clustering to minimize the sum of radii

DOI10.1137/100798144MaRDI QIDQ2884573zbMATH OpenOpenAlexFDO

Authors Gaurav Kanade, Imran A. Pirwani, Matt Gibson, Erik Krohn, Kasturi Varadarajan

Publication date 30 May 2012

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/100798144

zbMATH Keywords

\(k\)-clusteringMIN-cost \(k\)-coverminimum sum of radii cover

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Recommendations

• On Metric Clustering to Minimize the Sum of Radii
• On metric clustering to minimize the sum of radii
• Algorithms – ESA 2005
• On minimum sum of radii and diameters clustering
• The discrete 2-center problem

Cited in

(21)

• Clustering to minimize the maximum intercluster distance
• Clustering to minimize the sum of cluster diameters
• Average case network lifetime on an interval with adjustable sensing ranges
• A PTAS for the disk cover problem of geometric objects
• Fault-tolerant covering problems in metric spaces
• On Metric Clustering to Minimize the Sum of Radii
• Static and Dynamic Algorithms for k-Point Clustering Problems
• On minimum sum of radii and diameters clustering
• Faster algorithms for some optimization problems on collinear points
• Algorithms – ESA 2005
• Maximizing the sum of radii of disjoint balls or disks
• Covering a set of points with a minimum number of equal disks via simulated annealing
• Approximating fair \(k\)-min-sum-radii in Euclidean space
• Clustering with few disks to minimize the sum of radii
• FPT approximation for capacitated sum of radii
• Improved polynomial-time approximations for clustering with minimum sum of radii or diameters
• Approximation algorithms for clustering with minimum sum of radii, diameters, and squared radii
• FPT approximation for capacitated sum of radii
• Polynomial-time constant-approximation for fair sum-of-radii clustering
• Improved FPT approximation for sum of radii clustering with mergeable constraints
• On metric clustering to minimize the sum of radii

This page was built for publication: On clustering to minimize the sum of radii

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2884573)