Dynamic clustering to minimize the sum of radii

DOI10.4230/LIPICS.ESA.2017.48MaRDI QIDQ5111737zbMATH OpenFDO

Authors Dariusz Leniowski, Claire Mathieu, Monika R. Henzinger

Publication date 27 May 2020

Full work available at URL https://arxiv.org/abs/1707.02577

zbMATH Keywords

approximationclusteringdoubling dimensiondynamic algorithm

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Discrete location and assignment (90B80)

Recommendations

• Dynamic clustering to minimize the sum of radii
• Dynamic sum-radii clustering
• Online sum-radii clustering
• Online sum-radii clustering
• Clustering to minimize the sum of cluster diameters

Cites work

• Approximate clustering via metric partitioning
• Approximation algorithms for clustering to minimize the sum of diameters
• Cluster analysis and mathematical programming
• Clustering to minimize the sum of cluster diameters
• Design of dynamic algorithms via primal-dual method
• Deterministic fully dynamic approximate vertex cover and fractional matching in \(O(1)\) amortized update time
• Deterministic fully dynamic data structures for vertex cover and matching
• Fully dynamic approximate maximum matching and minimum vertex cover in O(^3 n) worst case update time
• Fully dynamic maximal matching in O( n) update time
• Graph clustering
• scientific article; zbMATH DE number 5764795 (Why is no real title available?)
• scientific article; zbMATH DE number 6469222 (Why is no real title available?)
• Minimum sum of diameters clustering
• Minimum-cost coverage of point sets by disks
• New deterministic approximation algorithms for fully dynamic matching
• On Metric Clustering to Minimize the Sum of Radii
• On minimum sum of radii and diameters clustering
• Online and dynamic algorithms for set cover
• Online clustering with variable sized clusters
• Online sum-radii clustering
• Partitioning the Nodes of a Graph to Minimize the Sum of Subgraph Radii
• Polynomial time approximation schemes for base station coverage with minimum total radii
• The Design of Competitive Online Algorithms via a Primal—Dual Approach

Cited in

(11)

• Clustering to minimize the sum of cluster diameters
• Dynamic clustering to minimize the sum of radii
• Online sum-radii clustering
• Online sum-radii clustering
• Dynamic sum-radii clustering
• Dynamic Digraph Connectivity Hastens Minimum Sum-of-Diameters Clustering
• scientific article; zbMATH DE number 7378709 (Why is no real title available?)
• Approximation algorithms for clustering with dynamic points
• On the Facility Location Problem in Online and Dynamic Models.
• Fully dynamic clustering and diversity maximization in doubling metrics
• Approximating fair \(k\)-min-sum-radii in Euclidean space

This page was built for publication: Dynamic 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 Q5111737)