Approximation Algorithms for Min-Sum k-Clustering and Balanced k-Median.
Babak BehsazZachary FriggstadMohammad R. SalavatipourRohit SivakumarPublished in: ICALP (1) (2015)
Keyphrases
- approximation algorithms
- np hard
- min sum
- constant factor approximation
- special case
- vertex cover
- clustering algorithm
- worst case
- clustering method
- k means
- primal dual
- minimum cost
- approximation ratio
- optimal solution
- data clustering
- undirected graph
- spectral clustering
- constant factor
- scheduling problem
- integer programming
- level set
- lower bound