Approximating min-max k-clustering

Summary

A 2-approximation algorithm for set partitioning into clusters with minimum of the maximum cost of a cluster, and a lower bound of k on the performance guarantee of any polynomial-time algorithm is shown.

Keywords

Oracle, Approximation algorithm, Monotone polygon, Combinatorics, Function (biology)

References

Clustering to Minimize the Maximum Intercluster DistanceTeofilo F. Gonzalez — 1985
Easy and hard bottleneck location problemsWen−Lian Hsu, George L. Nemhauser — 1979
When are NP-hard location problems easy?Dorit S. Hochbaum — 1984
Cluster analysis and mathematical programmingPierre Hansen, Brigitte Jaumard — 1997
A unified approach to approximation algorithms for bottleneck problemsDorit S. Hochbaum, David B. Shmoys — 1986
Optimal algorithms for approximate clusteringTomás Feder, Daniel Greene — 1988
Partitioning points and graphs to minimize the maximize or the sum of diametersClyde Monma — 1988

Cited by

No citing papers recorded for this paper.

Related papers

On the Performance of Smith’s Rule in Single-Machine Scheduling with Nonlinear CostWiebke Höhn, Tobias Jacobs — 2015
Minimizing machine assignment costs over Δ-approximate solutions of the scheduling problem P||CmaxAlina Kononov, Mikhail Y. Kovalyov, Bertrand M.T. Lin — 2019
Tight approximation algorithms for maximum general assignment problemsLisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni — 2006
Playing Games with Approximation AlgorithmsSham M. Kakade, Adam Tauman Kalai, Katrina Ligett — 2009