Approximation Algorithms for Min-Sum k-Clustering and Balanced k-Median.
Babak BehsazZachary FriggstadMohammad R. SalavatipourRohit SivakumarPublished in: Algorithmica (2019)
Keyphrases
- approximation algorithms
- np hard
- min sum
- constant factor approximation
- special case
- minimum cost
- clustering method
- vertex cover
- k means
- worst case
- clustering algorithm
- approximation ratio
- scheduling problem
- constant factor
- information theoretic
- undirected graph
- computational complexity
- primal dual
- data clustering
- mathematical model
- lower bound