Subexponential Algorithms for Continuous Euclidean $k$-Means in Subpolylogarithmic Dimension
Abstract · 22 pages
Given $n$ points in $\mathbb{Q}^d$ and an integer $k$, the continuous Euclidean $k$-means problem asks for $k$ centers in $\mathbb{R}^d$ that minimize the sum of squared distances from the input points to their nearest centers. In one dimension, the problem can be solved in polynomial time by dynamic programming. In higher dimensions, the algorithm of Inaba, Katoh, and Imai [SoCG 1994] runs in polynomial time when both $k$ and $d$ are fixed. Mahajan, Nimbhorkar, and Varadarajan [TCS 2012] showed that the problem is NP-hard even in the plane when $k$ is part of the input, answering a question of Dasgupta [2008]. In this paper, we give a deterministic exact algorithm for continuous Euclidean $k$-means. For arbitrary $k$ and $d=(\log n)^{o(1)}$, the algorithm runs in $O^*(2^{o(n)})$ time and uses polynomial space. Aman, Karthik C. S., and Punna [ESA 2024] asked whether the $2^n$ time bound for Euclidean $k$-means can be improved in high dimensions. Our result gives an affirmative answer to the corresponding question in subpolylogarithmic dimension.