2017/08/24 by Vincent Cohen-Addad, Cohen-Addad, Vincent
Computer Science · #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.CG #cs.DS
paper · pdf · doi:10.48550/arxiv.1708.07381
arxiv created 2017/08/29 · arxiv updated 2017/08/30
We consider the popular k-means problem in d-dimensional Euclidean space. Recently Friggstad, Rezapour, Salavatipour [FOCS'16] and Cohen-Addad, Klein, Mathieu [FOCS'16] showed that the standard local search algorithm yields a (1+ε)-approximation in time (n ⋅ k)^1/εO(d), giving the first polynomial-time approximation scheme for the problem in low-dimensional Euclidean space. While local search achieves optimal approximation guarantees, it is not competitive with the state-of-the-art heuristics such as the famous k-means++ and D2-sampling algorithms. In this paper, we aim at bridging the gap between theory and practice by giving a (1+ε)-approximation algorithm for low-dimensional k-means running in time n ⋅ k ⋅ (log n)^(dε-1)O(d), and so matching the running time of the k-means++ and D2-sampling heuristics up to polylogarithmic factors. We speed-up the local search approach by making a non-standard use of randomized dissections that allows to find the best local move efficiently using a quite simple dynamic program. We hope that our techniques could help design better local search heuristics for geometric problems. We note that the doubly exponential dependency on d is necessary as k-means is APX-hard in dimension d = ω(log n).