Clustering to minimize the sum of cluster diameters

DOI10.1016/j.jcss.2003.07.014zbMath1091.68099OpenAlexW4210565129MaRDI QIDQ1887718

Rina Panigrahy, Moses Charikar

Publication date: 22 November 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2003.07.014

zbMATH Keywords

greedy algorithmclustering points

Mathematics Subject Classification ID

Pattern recognition, speech recognition (68T10)

Related Items (25)

Algorithms for covering multiple submodular constraints and applications ⋮ Fault-tolerant covering problems in metric spaces ⋮ Approximation algorithms for the minimum power cover problem with submodular/linear penalties ⋮ An incremental version of the \(k\)-center problem on boundary of a convex polygon ⋮ Online clustering with variable sized clusters ⋮ Unnamed Item ⋮ On Metric Clustering to Minimize the Sum of Radii ⋮ On the parameterized complexity of clustering problems for incomplete data ⋮ Connecting a set of circles with minimum sum of radii ⋮ Maximum gradient embeddings and monotone clustering ⋮ Dynamic clustering to minimize the sum of radii ⋮ Dynamic Sum-Radii Clustering ⋮ Graph clustering ⋮ Reallocating multiple facilities on the line ⋮ Locating Facilities on a Network to Minimize Their Average Service Radius ⋮ Online sum-radii clustering ⋮ On minimum sum of radii and diameters clustering ⋮ MULTI COVER OF A POLYGON MINIMIZING THE SUM OF AREAS ⋮ On metric clustering to minimize the sum of radii ⋮ The structural clustering and analysis of metric based on granular space ⋮ Unnamed Item ⋮ Multi Cover of a Polygon Minimizing the Sum of Areas ⋮ Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks ⋮ Maximizing the ratio of cluster split to cluster diameter without and with cardinality constraints ⋮ A primal-dual approximation algorithm for the \(k\)-prize-collecting minimum power cover problem

Cites Work

• A simple heuristic for the p-centre problem
• Approximation algorithms for geometric median problems
• Approximation algorithms for min-sum \(p\)-clustering
• Cluster analysis and mathematical programming
• A constant-factor approximation algorithm for the k -median problem (extended abstract)
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• A Best Possible Heuristic for the k-Center Problem
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• Approximating min-sum k -clustering in metric spaces
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Clustering to minimize the sum of cluster diameters