{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreifoverh2lh6y24bz5gvmd6edxa7yhev64oqm7kchwrom2h32mwks4",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3miei5oqldow2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.28268v1",
  "publishedAt": "2026-03-31T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Vincent Cohen-Addad",
    "Karthik C. S.",
    "David Saulpic",
    "Chris Schwiegelshohn"
  ],
  "textContent": "**Authors:** Vincent Cohen-Addad, Karthik C. S., David Saulpic, Chris Schwiegelshohn\n\nThe $k$-means problem is a classic objective for modeling clustering in a metric space. Given a set of points in a metric space, the goal is to find $k$ representative points so as to minimize the sum of the squared distances from each point to its closest representative. In this work, we study the approximability of $k$-means in Euclidean spaces parameterized by the number of clusters, $k$. In seminal works, de la Vega, Karpinski, Kenyon, and Rabani [STOC'03] and Kumar, Sabharwal, and Sen [JACM'10] showed how to obtain a $(1+\\varepsilon)$-approximation for high-dimensional Euclidean $k$-means in time $2^{(k/\\varepsilon)^{O(1)}} \\cdot dn^{O(1)}$. In this work, we introduce a new fine-grained hypothesis called Exponential Time for Expanders Hypothesis (XXH) which roughly asserts that there are no non-trivial exponential time approximation algorithms for the vertex cover problem on near perfect vertex expanders. Assuming XXH, we close the above long line of work on approximating Euclidean $k$-means by showing that there is no $2^{(k/\\varepsilon)^{1-o(1)}} \\cdot n^{O(1)}$ time algorithm achieving a $(1+\\varepsilon)$-approximation for $k$-means in Euclidean space. This lower bound is tight as it matches the algorithm given by Feldman, Monemizadeh, and Sohler [SoCG'07] whose runtime is $2^{\\tilde{O}(k/\\varepsilon)} + O(ndk)$. Furthermore, assuming XXH, we show that the seminal $O(n^{kd+1})$ runtime exact algorithm of Inaba, Katoh, and Imai [SoCG'94] for $k$-means is optimal for small values of $k$.",
  "title": "Near-Optimal Bounds for Parameterized Euclidean k-means"
}