Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms

Authors:
  • SASara Ahmadian
    Sara Ahmadian
  • ANAshkan Norouzi-Fard
    Ashkan Norouzi-Fard
  • OSOla Svensson
    Ola Svensson
  • JWJustin Ward
    Justin Ward

Abstract
Clustering is a classic topic in optimization with $k$-means being one of the most fundamental such problems. In the absence of any restrictions on the input, the best-known algorithm for $k$-means...
Funding Information
  • H2020 European Research Council (335288)

This publication has 15 references indexed in Scilit: