Near-Optimal Bounds for Parameterized Euclidean k-Means

Cohen-Addad, Vincent; C. S., Karthik; Saulpic, David; Schwiegelshohn, Chris

doi:10.4230/LIPIcs.SoCG.2026.33

Near-Optimal Bounds for Parameterized Euclidean k-Means

Vincent Cohen-Addad

Google Research, New York, NY, USA Karthik C. S

Rutgers University, Piscataway, NJ, USA David Saulpic

Université Paris Cité, CNRS, IRIF, F-75013, Paris, France Chris Schwiegelshohn

Aarhus University, Denmark

Abstract

The $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^{\widetilde{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$ .

Keywords and phrases:

k-means clustering, Euclidean space, Fine-Grained Complexity

Funding:

Karthik C. S.: This work was supported by the National Science Foundation under Grants CCF-2313372 and CCF-2443697, a grant from the Simons Foundation, Grant Number 825876, Awardee Thu D. Nguyen, and partially funded by the Ministry of Education and Science of Bulgaria’s support for INSAIT, Sofia University “St. Kliment Ohridski” as part of the Bulgarian National Roadmap for Research Infrastructure.

Chris Schwiegelshohn: This work was partially supported by the Independent Research Fund Denmark (DFF) under a Sapere Aude Research Leader grant No 1051-00106B and by a Google Research Award.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Facility location and clustering ; Theory of computation

\rightarrow

Computational geometry

Related Version:

Full Version: https://arxiv.org/abs/2603.28268

Acknowledgements:

We thank Dor Minzer, Euiwoong Lee, and Pasin Manurangsi for several discussions that helped conceptualize the proof approach in this paper.

DOI:

10.4230/LIPIcs.SoCG.2026.33

Event:

42nd International Symposium on Computational Geometry (SoCG 2026)

Editors:

Hee-Kap Ahn, Michael Hoffmann, and Amir Nayyeri

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

The $k$ -clustering problem represents a fundamental task in data mining and machine learning, providing a model for grouping data points based on similarity. Given a set of points $P$ in a metric space $(X,\Delta)$ , the objective is to select a set $C\subseteq X$ of $k$ points, referred to as centers, and the goal is to minimize an objective function typically defined as the sum of the $z$ -th powers of the distances from each point $p\in P$ to its nearest center in $C$ . This general formulation encompasses several widely studied problems: $k$ -median corresponds to $z=1$ , $k$ -means uses $z=2$ (minimizing the sum of squared distances), and $k$ -center is when $z\rightarrow\infty$ (minimizing the maximum distance).

The algorithmic exploration of $k$ -means, arguably the most popular variant, gained significant traction with the seminal work of Lloyd [49]. Since then, the problem has attracted substantial attention across diverse research communities, including operations research, machine learning, and theoretical computer science.

The computational complexity of $k$ -means problem inherently depends on the structure of the underlying metric space $(X,d)$ and this paper focuses on the setting where points reside in Euclidean space $\mathbb{R}^{d}$ . From a complexity theoretic perspective, Euclidean $k$ -means is known to be NP-Hard even under seemingly restricted conditions, such as when the points lie in the Euclidean plane ( $\mathbb{R}^{2}$ ) but $k$ is part of the input [58, 51], or when $k=2$ but the dimension $d$ is large [24, 5]. On the algorithmic side, the best-known exact algorithm for Euclidean $k$ -means was proposed by Inaba, Katoh, and Imai [40], running in time ${O}(n^{kd+1})$ . Remarkably, this has remained the state-of-the-art exact algorithm for over three decades.

Given the hardness of finding exact solutions, particularly in high dimensions, a significant line of research has focused on developing efficient $(1+\varepsilon)$ -approximation algorithms. Early breakthroughs by Fernandez de la Vega, Karpinski, Kenyon, and Rabani [30] and Kumar, Sabharwal, and Sen [46] demonstrated that a $(1+\varepsilon)$ -approximation for high-dimensional Euclidean $k$ -means could be achieved in time $2^{(k/\varepsilon)^{{O}(1)}}\cdot dn^{{O}(1)}$ . Subsequent improvements, leveraging techniques such as coresets by Feldman, Monemizadeh, and Sohler [29], refined the runtime to ${O}(ndk)+2^{\widetilde{{O}}(k/\varepsilon)}$ . Further work by Jaiswal, Kumar, and Sen [42], followed by Jaiswal, Kumar, and Yadav [43], utilized a simpler approach based on $D^{2}$ -sampling to achieve ${O}(nd\cdot 2^{\widetilde{{O}}(k/\varepsilon)})$ runtime (see also [1, 10] for a generalized approach).

All these different approaches seem to have hit a running-time barrier at $2^{k/\varepsilon}$ (up to logarithmic factors in the exponent). This contrasts sharply with the related $k$ -center problem, where Agarwal and Procopiuc [4] showed that a $(1+\varepsilon)$ -approximation can be obtained much faster, in time $n\log k+(k/\varepsilon)^{{O}(k^{1-1/d})}$ . This runtime for $k$ -center is known to be essentially optimal under the Exponential Time Hypothesis (ETH) [13]. Furthermore, there exists a close relationship between $k$ -means and the Partial Vertex Cover (PVC) problem; indeed, many known hard instances for $k$ -means are derived from hard PVC instances [7, 48, 18]. Interestingly, Manurangsi [53] demonstrated that PVC admits a $(1+\varepsilon)$ -approximation in time $\varepsilon^{-{O}(k)}n^{{O}(1)}$ (where $k$ is the solution size). This implies that the specific $k$ -means instances derived from PVC can be approximated more efficiently than the runtime of the current best $(1+\varepsilon)$ -approximation algorithms for Euclidean $k$ -means.

This discrepancy motivates the central question of our work: When parameterized by the number of clusters $k$ , is the current exponential dependency in $k/\varepsilon$ for approximating Euclidean $k$ -means inherent, signifying a fundamental computational gap compared to $k$ -center and PVC-related instances? Or, is it possible to devise a significantly faster approximation algorithm, potentially achieving a runtime closer to those known for related problems and offering a more unified algorithmic picture for $k$ -clustering? More concretely:

Question 1.

Is it possible to design a $(1+\varepsilon)$ -approximation to $k$ -means running in time $O(nd)+\varepsilon^{-O(k)}$ ?

A negative answer to the above question would also imply progress toward understanding the hardness of exact algorithms. Currently, we are not aware of any fine-grained lower bound that matches the algorithm of Inaba et al. [40]. The closest result we know of is by Cohen-Addad, de Mesmay, Rotenberg, and Roytman [14], who showed that if the centers must be selected from a prescribed set of “candidate centers”, then no exact algorithm with a runtime of $n^{o(k)}$ exists for $k$ -median or $k$ -means, even when the dimension is four. It remains an open problem whether a similar result holds for the classic version where centers can be placed anywhere in $\mathbb{R}^{d}$ , and whether an $n^{o(d)}$ lower bound also applies when $k$ is constant.

A negative answer to Question 1 would answer those two questions: modern dimension-reduction [52] and coreset computation [23] reduce the dimension and the number of distinct input points while preserving the clustering cost within a $(1\pm\varepsilon)$ factor. Thus, as we show in the full version, any lower bound for approximation algorithms translates into a lower bound for exact algorithms, making progress toward demonstrating the optimality of [40].

Negative answers to such questions typically arise from fine-grained complexity assumptions, such as the Exponential Time Hypothesis (ETH) [38, 39], or the more modern Gap Exponential Time Hypothesis (Gap-ETH) [55, 26]. Indeed these two assumptions have been very fruitful in explaining the intractability of various important geometric optimization problems [56, 50, 25, 45]. However, Question 1 involves two parameters, $k$ and $\varepsilon$ . Suppose we aim to rule out $2^{(k/\varepsilon)^{1-o(1)}}\cdot\text{poly}(n,d)$ -time algorithms, then our parameter of interest is the quantity $k/\varepsilon$ , where $k$ and $\varepsilon$ are free variables constrained only by the fixed ratio $k/\varepsilon$ . To the best of our knowledge, such results are not known under ETH or Gap-ETH. In fact, proving such results entail several technical challenges which we discuss in Section 2.1.

1.1 Our Results

In this paper we make substantial progress towards answering these questions. We introduce a hypothesis morally capturing a Gap Exponential Time Hypothesis for Vertex Cover on Near Perfect Vertex Expanders, and we call it Exponential Time for Expanders Hypothesis (denoted XXH). This hypothesis is formally stated in Section 3, but an informal discussion about the statement of this hypothesis is given in Section 2.2. Assuming XXH, we are able to answer Question 1 in the following way:

Theorem 2 (Answer to Question 1; informal statement).

Assuming XXH, for every $\beta>0$ , there is no randomized algorithm running in time $2^{\left(k/\varepsilon\right)^{1-\beta}}\cdot\mathrm{poly}(n,d)$ that can $(1+\varepsilon)$ -approximate the Euclidean $k$ -means problem whenever $k\gg 1/\varepsilon$ .

The formal statement of the lower bound is Theorem 12. This result might appear surprising due to the known close connection between vertex cover and $k$ -means. Specifically, a partial vertex cover can be approximated within a $(1+\varepsilon)$ factor in $\varepsilon^{-O(k)}n^{O(1)}$ time [53] (where $k$ is the solution size). This might lead one to expect an approximation scheme for $k$ -means with similar complexity.

For example, reductions such as those in Cohen-Addad et al. [14] and Awasthi et al. [7] (see also [48]) transform the vertex cover instance into a $k$ -means instance by creating a point for each edge of the input graph and positioning the points in space such that pairs of edges sharing a common vertex are close to each other. The hardness proof then relies on distinguishing between two kinds of instances:

(1)

Instances derived from graphs admitting a vertex cover of size $k$ , i.e., the edge set can be partitioned to $k$ stars. In this case, the corresponding point set can be partitioned into $k$ clusters such that all points within the same cluster are close (say distance 1, representing edges covered by the same vertex from the cover).
(2)

Instances derived from graphs where any set of $k$ vertices leaves at least a constant fraction (say $\delta$ fraction) of the edges uncovered. Consequently, in any partitioning of the corresponding point set into $k$ clusters, either a constant fraction of these clusters contain points that are far apart (say distance 3, i.e., representing pairs of edges that do not share one of the selected $k$ vertices) or a few clusters contain a lot of points (and most pairs are far apart).

The hardness for $k$ -means then follows from the difficulty of distinguishing between these two cases based on the clustering cost. Specifically, it involves separating instances admitting a lower cost (e.g., $n$ , associated with Case 1) from those necessitating a higher cost (e.g., $(1-\delta)n+2\delta n=n+\delta n$ , associated with Case 2), where $\delta$ is related to the minimum fraction of uncovered edges in the latter case.

However, since partial vertex cover can be approximated within a $(1+\varepsilon)$ factor, for any $\varepsilon>0$ , in time $\varepsilon^{-O(k)}n^{O(1)}$ , and since the objective scales linearly with the number of edges not covered (i.e., clients that are at squared distance 3, instead of 1, from their center), this type of instance can be solved in time $\varepsilon^{-O(k)}n^{O(1)}$ . Therefore, one cannot expect to boost the lower bound running time from the partial vertex cover result to $2^{(k/\varepsilon)^{1-o(1)}}$ .

Thus, to show that the $k$ -means problem requires an exponential dependency in $\varepsilon$ , we need to develop a novel reduction framework.

To establish the above conditional lower bound for the Euclidean $k$ -means problem, we first reduce the vertex cover problem in the non-parameterized setting to an intermediate graph problem, essentially in the parameterized setting, but with reduced structure so as to fail standard algorithmic techniques for partial $k$ -vertex cover, while retaining enough structure to embed the graph problem into the Euclidean $k$ -means problem. We direct the reader to Section 2 for further details where we also try to clarify how vertex expansion in the vertex cover problem helps us overcome several technical difficulties.

Theorem 2 implies lower-bounds for exact algorithms as well:

Corollary 3.

Assuming XXH, for every $\beta>0$ , there is no algorithm that for any $k, d$ solves the Euclidean $k$ -means problem in time $n^{(k\sqrt{d})^{1-\beta}}$ , nor in time $n^{d^{1-\beta}}$ .

Note that this result contrasts the running time of $k$ -means clustering with that of $k$ -center, which admits an exact algorithm running in time $O\left(n^{k^{1-1/d}}\right)$ [4]. The current state of the art algorithm enumerating over all Voronoi partitions in time $O(n^{kd+1})$ by Inaba, Katoh and Imai [40] is thus a likely candidate for being optimal – in particular, it is almost optimal for constant $k$ .

1.2 Further Related Work

Hardness of Clustering.

As we mentioned previously, the $k$ -means and $k$ -median problems are NP-hard, even when $k=2$ (and $d$ is large) [24, 5], or when $d=2$ (and $k$ is large) [58, 51]. When both parameters are part of the input, the problems become APX-hard [32, 41, 33, 7, 19, 20]. Most techniques to show hardness of approximation are based on reducing from covering problems to clustering problems, for instance through structured instances of max $k$ -coverage or set cover. Recent works have used different approaches: [19] showed how to use hardness of some coloring problems to prove hardness of approximation for $k$ -median and $k$ -means in general metric spaces, and [20] focused on Euclidean spaces and tried to pinpoint what combinatorial structures allow for gap-preserving embeddings to Euclidean space.

For general metrics, the connection between $k$ -clustering and the set cover problem (or rather max-coverage) has been known since the fundamental work of Guha and Khuller [32], who established the best known hardness of approximation bounds. This connection was observed again when analyzing the parameterized complexity of the problem: Cohen-Addad, Gupta, Kumar, Lee and Li [17] showed how to approximate $k$ -median and $k$ -means up to factors $1+2/e$ and $1+8/e$ respectively and showed that this is tight assuming Gap-ETH (see also [22, 54, 3, 12, 35]).

FPT algorithms via Sketching.

The past decades have seen the development of very powerful sketching and compression methods that allow reducing the dimension to $O(\log k/\varepsilon^{2})$ [52] and the number of distinct input points to $\widetilde{O}(k\varepsilon^{-z-2})$ ( $z=1$ for $k$ -median, $z=2$ for $k$ -means) via the construction of coresets [28, 11, 37, 23, 21]. Perhaps surprisingly, these bounds are independent of the original input size and dimension and can be computed in near-linear time, which allows for the construction of simple FPT algorithms. Applying the $O(n^{kd+1})$ algorithm of [40] indeed gives a complexity of $2^{\widetilde{O}(k/\varepsilon^{2})}$ plus the near-linear time to sketch the input; naively enumerating all partitions yields a running time of $k^{\widetilde{O}(k/\varepsilon^{z+2})}$ , plus the time to sketch the input.

We crucially remark that the dependency on $\varepsilon$ cannot be substantially improved: [21] showed a lower bound of $\Omega(k\varepsilon^{-2})$ for coresets, and [47] showed the optimality of the dimension reduction. Therefore, one cannot hope to go below $2^{\Omega(k/\varepsilon^{2})}$ and answer Question 1 using only these techniques.

Other parameters were studied for $k$ -means clustering: most notably, the cost has been investigated by Fomin, Golovach and Simonov [31]. They presented a $D^{D}\mathrm{poly}(nd)$ exact algorithm for $k$ -median, where $D$ is an upper bound on the cost.

From Continuous to Discrete Clustering.

The other standard technique to design FPT algorithms is to find a small set of candidate centers that contains a near-optimal solution. This approach was used, for instance, by [8] to obtain the first algorithm running in time $2^{(k/\varepsilon)^{O(1)}}d^{O(1)}n\log^{O(k)}(n)$ , by [46] to improve the running time, and by [9] for the capacitated clustering problem.

Approximation Algorithms in Euclidean Spaces.

To compute a $(1+\varepsilon)$ -approximation in time polynomial in $n$ and $k$ , any algorithm must have a running time at least doubly exponential in $d$ , as the problem is APX-hard in dimension $\Omega(\log n)$ . The best of these algorithms is from [16], with a near-linear running time of $f(\varepsilon,d)n\operatorname{polylog}n$ . If one sticks to algorithms polynomial in $n, k$ and $d$ , the lower bounds on the approximation ratio are $1.06$ for $k$ -median and $1.015$ for $k$ -means, conditioned on P $\neq$ NP [20]. The upper bounds are still quite far: $2.41$ for $k$ -median, and $5.96$ for $k$ -means [15].

2 Our Techniques

We would like to now convey the conceptual and technical ideas that went into proving the lower bound in Theorem 2. As alluded to earlier in this section, hard instances of Euclidean $k$ -means are typically constructed from the Vertex Cover problem, where every edge is mapped to a client and the partition of the edge set (which is the client set) by an optimal vertex cover also yields the optimal clustering for the $k$ -means objective.

2.1 Motivation and Technical Background

Current Understanding of the Landscape.

Starting from Gap-ETH (for 3-SAT) [26, 55], it is easy to show that there is no $2^{o(n)}$ time algorithm to $1+\delta$ approximate the Vertex Cover problem (on sparse graphs) for some small constant $\delta>0$ . By a standard reduction, this implies that Euclidean $k$ -means cannot be approximated within $1+\delta$ in time $2^{o(n)}$ , albeit when $k$ is linear in $n$ (the number of clients). On the other hand, starting from ETH [38, 39], it is easy to show (for example following the reduction in [24] or [5]) that Euclidean $2$ -means cannot be exactly solved in $2^{o(n)}$ time. Thus, we can show that there is no $2^{o(k/\varepsilon)}\cdot\mathrm{poly}(n)$ time algorithm for $1+\varepsilon$ approximating Euclidean $k$ -means problem, when either (i) $k=\Omega(n)$ and $\varepsilon=\Omega(1)$ , or (ii) $k=2$ and $\varepsilon=1/\Omega(n)$ .

Exploring Uncharted Territories.

From the above discussion, we know that if $k$ was $\Omega(n)$ then we cannot obtain a $2^{o(n)}$ time approximation algorithm, but what if $k$ was approximately $\sqrt{n}$ ? Then algorithmic techniques based on coresets yield a $(1+\varepsilon)$ approximation in time $2^{\widetilde{O}(\sqrt{n}/\varepsilon)}$ . But is it possible to do better?

We can try to answer this from the lower bound viewpoint. We can look at the above mentioned Gap-ETH hard instance, i.e., the setting $k=\Omega(n)$ and $\varepsilon=\Omega(1)$ and duplicate each point $n$ times to obtain a point-set with $N=n^{2}$ points, and we have that there is no $2^{\sqrt{N}}$ time algorithm that can constant approximate the objective. But we cannot even rule out the possibility that there is an exact algorithm running in time $2^{N^{0.51}}$ for this value of $k$ . Ideally, we would like to be able to rule out algorithms running in time $2^{N^{0.5+\rho}}$ that provide a $(1+\Omega(1/N^{\rho}))$ approximate solution, for every $\rho\in[0,0.5]$ . Thus, the result that we are shooting for is:

Rule out $2^{o(k/\varepsilon)}\cdot\mathrm{poly}(n)$ time algorithms, when $k/\varepsilon$ is fixed,

i.e., we want the lower bound to hold on the entire tradeoff curve between the number of clusters $k$ and the accuracy of clustering $\varepsilon$ . To the best of our knowledge, there are no such results known in fine-grained complexity. Thus, we are motivated to develop a new framework to prove such results.

Technical Challenges.

One approach is to start from the lower bound given in $(ii)$ , i.e., when $k=2$ and $\varepsilon=1/\Omega(n)$ , and reduce it to a different instance of $k$ -means, where $k$ has increased (say to $\sqrt{n}$ ), but also $\varepsilon$ has increased to $1/\sqrt{n}$ (all this with a linear blowup in size). But this requires “gap creation”, a notorious challenging task, potentially much harder than even proving Gap-ETH from ETH!

Therefore, we pursue the approach of starting from the lower bound given in $(i)$ , i.e., when $k=\Omega(n)$ and $\varepsilon=\Omega(1)$ , and reduce it to a different instance of $k$ -means, where $k$ has decreased (say to $\sqrt{n}$ ), and $\varepsilon$ has also decreased to $1/\sqrt{n}$ . This is the approach of trading off the gap to reduce the number of clusters.

A (Failed) Simple Approach.

Let $G=([n],E)$ be a vertex cover instance (where $|E|:=m=O(n)$ ) which is hard to approximate to $1+\delta$ factor (for some positive constant $\delta$ ) under Gap-ETH. Thus, size of an optimal vertex cover of $G$ , denoted $\alpha_{G}$ is $\Omega(n)$ . Suppose, our target $k$ -means instance is when $k=o(m)$ and $\varepsilon=\Omega(\delta k/\alpha_{G})$ : then we may simply look at the embedding where each edge $\{u,v\}\in E$ is mapped to the point (i.e., client), $\mathbf{e}_{u}+\mathbf{e}_{v}\in\mathbb{R}^{n}$ , where $\mathbf{e}_{i}$ is the standard basis vector which is 1 on $i^{\text{th}}$ coordinate, and 0 everywhere else. If we were asked to cluster this client set to $\alpha_{G}$ clusters minimizing the $k$ -means objective in Euclidean metric, then the optimal solution would simply be the partition based on some optimal vertex cover of $G$ . Thus, we could hope that even when asked to cluster the clients to $k$ parts, the optimal solution would be to first cluster the clients into $\alpha_{G}$ clusters (based on the vertex cover) and then merge clusters, so as to end up with only $k$ clusters in the end. However, since $k\ll\alpha_{G}$ , we can have near-optimal cost from clustering which do not correspond to any vertex cover of $G$ . For example, a typical obstacle is when we have the following clustering: $k-1$ clusters each contain a single client, and one cluster contains all the remaining points. It is entirely possible that such clusterings also have low cost.

Embedding via Color Coding.

To overcome the above issue (of imbalancedness) of clustering, we introduce a color coding based embedding technique. Given $G$ and a target number of clusters $k$ , we first uniformly and independently randomly color each vertex $v$ in $G$ , with a color in $[k]$ (and let color of $v$ be denoted by $c_{v}$ ). Thus each edge (consisting of two vertices), also gets (at most) two colors. Now, consider the embedding where each edge $\{u,v\}\in E$ is mapped to the point (i.e., client), $\mathbf{e}_{u}+\mathbf{e}_{v}+\mathbf{e}_{c_{u}}+\mathbf{e}_{c_{v}}\in\mathbb{% R}^{n+k}$ . Consider the clustering of this client set to $k$ parts in the following way. Let $S\subset[n]$ be any optimal vertex cover of $G$ and $S:=S_{1}\dot{\cup}\cdots\dot{\cup}S_{k}$ be a partition of the vertices in the vertex cover based on the coloring. Then the alleged optimal clusters would be given by the edges covered by $S_{1},\ldots,S_{k}$ , i.e., cluster $i$ would be all edges (i.e., the corresponding points of these edges) in $G$ covered by the vertices in $S_{i}$ (break ties arbitrarily).

The embedding of the colors of the edges, forces the optimal clusters to have a dominating color, and since the colors are uniformly spread, the obstacle mentioned in the above approach (without coloring), would yield high clustering cost and thus can now be ruled out.

That said, there is a more serious obstacle that is not addressed: when we merge clusters in the completeness and soundness case, the graph topology affects the $k$ -means cost; we elaborate on this next.

Need for Vertex Expansion.

Consider two graphs $G_{1}$ and $G_{2}$ , both on $n$ vertices and are $d$ -regular. Suppose $G_{1}$ looks like a random $d$ regular graph, and thus is a very good vertex expander, and for every subset $S$ of vertices of size $O(n/d)$ we have that the number of unique neighbors is about $|S|\cdot(d-O(1))$ [59]. On the other hand suppose that $G_{2}$ is obtained by first taking $n/(2d-6)$ disjoint copies of $K_{d-3,d-3}$ and then adding a random $3$ -regular graph to connect these copies.

We encounter the following problem when we merge clusters as described above: $G_{1}$ behaves in the way we expect it to, whereas the $G_{2}$ has a very low cost even if it doesn’t have a good vertex cover. This is because if we take the $d-3$ sized independent set in a $K_{d-3,d-3}$ then we do get a very good vertex cover of $K_{d-3,d-3}$ but in addition if all (or even a large fraction of) the edges of $K_{d-3,d-3}$ were in the same cluster then each edge has $2d-8$ other edges that is adjacent to it in the cluster. On the other hand, if we take the edges incident to an independent set in $G_{1}$ , then a typical edge has $d-1$ other edges incident to it. This makes the analysis of completeness and soundness impossible without knowing more about the graph topology.

2.2 New Hypothesis: Exponential Time for Expanders Hypothesis

Exponential Time for Expanders Hypothesis (XXH).

To remedy the situation we introduce a working hypothesis that the gap vertex cover problem cannot be solved in time $2^{n^{1-o(1)}}$ on random graphs. For the sake of keeping the proofs clean (to the extent possible), we state the hypothesis in Section 3 in terms of vertex expanders which makes it directly usable. Under this hypothesis, we use the color coding embedding that was described earlier and with a lot of technical effort are able to derive the conclusion given in Theorem 2.

Informally, XXH asserts that for some constants $\zeta,\delta$ , such that $\zeta\ll\delta$ , no randomized algorithm running in $2^{n^{1-o(1)}}$ time can take as input a $d$ -regular vertex expander $G:=([n],E)$ and distinguish between the following:

Completeness:: There exist $n/2$ vertices that cover at least $(1-\zeta)$ fraction of $E$ .
Soundness:: Every subset of $V$ of size $n/2$ does not cover $\delta$ fraction of the edges.

Plausibility of XXH.

A key observation connecting random graphs and expander graphs is that random $d$ -regular graphs are known to be very strong vertex expanders with constant probability (see Theorem 4.2 in [59]). Consequently, making progress on understanding the inapproximability of the Vertex Cover problem on vertex expanders is closely related to the hardness of the vertex cover problem on random graphs.

XXH formalizes this hardness on vertex expanders and, via our main reduction (Theorem 12), links it directly to the Euclidean $k$ -means problem. This connection implies we live in one of three possible worlds. The first is where XXH is false and the Euclidean $k$ -means admits a much faster algorithm (such as $2^{(k/\varepsilon)^{0.99}}\cdot\mathrm{poly}(n)$ time), and this would yield new algorithms for computing Vertex Cover on random-like graphs. The second is where XXH is false but there are no new faster algorithms for Euclidean $k$ -means, and this would force a deeper, computational understanding of vertex expanders themselves. The third world is where XXH is true, and thus the current Euclidean $k$ -means algorithm is nearly optimal. The reader is directed to Section 3.2 for more discussion on these three possibilities.

Investigating the truth of XXH (the third world) leads to natural questions of independent interest. For instance, Ramanujan graphs are known to be near-perfect vertex expanders for small sets [57], so we ask: does the Vertex Cover problem admit a PTAS when the input graph is a Ramanujan graph? Progress on this question would directly help us better understand XXH.

As partial evidence for XXH, in Corollary 11 we show that if we forego the expansion property, then under the Unique Games Conjecture it is possible to show from [6] that no polynomial-time algorithm can take as input a $d$ -regular graph $G:=([n],E)$ and distinguish between the following:

Completeness:: There exist $n/2$ vertices that cover at least a $(1-\zeta)$ fraction of $E$ .
Soundness:: Every subset of $V$ of size $n/2$ fails to cover an $\Omega(\sqrt{\zeta})$ fraction of the edges.

Our Message.

We wish to highlight two key aspects of the XXH hypothesis. First, it fundamentally acts as a fine-grained complexity assumption regarding the hardness of the Vertex Cover problem on random instances. Second, it establishes an important connection: developing better approximation algorithms for Euclidean $k$ -means would provide non-trivial approaches to solving Vertex Cover on expander graphs, a problem of significant independent interest. In addition, even if weaker versions of XXH are true (and proved in the future), this would imply weaker lower bounds for $(1+\varepsilon)$ -approximating the Euclidean $k$ -means problem (see Remark 14 for details).

2.3 Proof Overview of Theorem 2

We now give an overview of the completeness and soundness cases. Recall that we are given a $d$ -regular graph $G=([n],E)$ , and we have constructed a point $\mathbf{e}_{u}+\mathbf{e}_{v}+\mathbf{e}_{c_{u}}+\mathbf{e}_{c_{v}}\in\{0,1\}^% {n+k}$ , for each edge $(u,v)$ whose end points have colors $c_{u}$ and $c_{v}$ .

In the completeness case, we have that there are $n/2$ vertices cover $1-\zeta$ fraction of edges, so our strategy to cluster is straightforward: first form $n/2$ clusters, each one corresponding to a vertex in the vertex cover solution, and then identify each cluster with a color by looking at the color of the common vertex in each cluster (which is a star graph). Then, each color class would be a cluster, and we have $k$ clusters, and we can show that the cost is $3|E|-(1-7\zeta)kd$ .

However, our soundness analysis is highly non-trivial, and involves several tools and arguments of different flavors. Suppose we have a clustering of $P$ whose $k$ -means cost is about $3|E|-(1-\delta^{5})kd$ (where $\zeta\leq\delta^{5}/10$ ), then we first connect the cost of cluster $C_{i}$ (for $i\in[k]$ ) with certain properties of the graph $G_{i}$ in the following way:

Lemma 4 (Informal statement).

For every cluster $C_{i}$ we have its cost is equal to:

\displaystyle 3|C_{i}|-1+(\gamma_{i}-\kappa_{i})(|C_{i}|-1)-\frac{1}{|C_{i}|}% \cdot\sum_{v\in V_{i}}d_{i,v}^{2},

where $d_{i,v}$ is the degree of $v$ in the graph $G_{i}$ (induced by edges in $C_{i}$ ), $\gamma_{i}$ is the fraction of pairs of edges in $G_{i}$ that have no color in common, and $\kappa_{i}$ is the fraction of pairs of edges that have two colors in common.

Next, we show that if $\gamma_{i}$ (fraction of pairs of edges with no color in common) and $\kappa_{i}$ (fraction of pairs of edges with two colors in common) are not too large, then there is a dominant single color in the cluster $C_{i}$ .

Lemma 5 (Informal statement).

If $\kappa_{i}$ and $\gamma_{i}$ are bounded by some small constants, then there is a large fraction of edges in $G_{i}$ that have the same color.

Then, we show that we can identify a large subcollection of clusters for which both $\kappa_{i}$ and $\gamma_{i}$ are small. In addition, we assume that the cost of the clustering $C_{1},\ldots,C_{k}$ is at most $3|E|-(1-\delta^{5})dk$ . Then, for each cluster in this subcollection, we can relate a bound on the sum of the squared degrees of the vertices in the subcollection to the clustering cost appearing in Lemma 4.

Lemma 6 (Informal statement).

There is some $I\subseteq[k]$ such that for all $i\in I$ , it holds that $\kappa_{i}$ and $\gamma_{i}$ are small and $\sum_{i\in I}|E_{i}|\geq(1-38\delta^{2})\cdot|E|$ . In addition, we also have for all $i\in I$ :

\displaystyle\frac{\sum_{v\in G_{i}}d_{i,v}^{2}}{\sum_{v\in G_{i}}d_{i,v}}\geq% (1-\delta^{3})\cdot\frac{d}{2}.

Finally, we show that a cost of clustering $3|E|-(1-\delta^{5})dk$ implies that we can construct a set of vertices $S\subseteq[n]$ of size slightly more than $n/2$ such that we cover $(1-10\delta^{1.5})$ fraction of the edges, contradicting the soundness assumption of XXH for small enough $\delta$ . This step is quite involved, and we skip providing more details about it here.

3 Exponential Time for Expanders Hypothesis

In this section, we formally introduce the Exponential Time for Expanders Hypothesis which is then used in the next section to prove conditional lower bounds for the Euclidean $k$ -means problems for small $k$ .

3.1 New Hypothesis: Exponential Time for Expanders Hypothesis

We first define the notion of vertex expansion relevant to this submission.

Definition 7 (Small Set Vertex Expanders).

Given constants $\alpha>0$ , a $d$ -regular graph $G=(V,E)$ on $n$ vertices, and an integer $k:=k(n)$ , we say that $G$ is a $(k,\alpha)$ -small set vertex expander if for every subset $S\subseteq V$ of size at most $n/k$ we have that $|\{u\in V:\exists\{u,v\}\in E\text{ and }v\in S\}|\geq(1-\alpha)\cdot d\cdot|S|$ .

Now, we can define our new hypothesis.

Hypothesis 8 (Exponential Time for Expanders Hypothesis – XXH $(\delta,\zeta,\alpha)$ ).

Given constants $\delta,\zeta,\alpha\in(0,1)$ , the XXH $(\delta,\zeta,\alpha)$ assumption states that the following holds for all $\beta>0$ : No randomized algorithm running in $2^{n^{1-\beta}}$ time can, given as input a $d$ -regular $(\mathrm{polylog}n,\alpha)$ -small set vertex expander $G=(V=[n],E)$ with $d=(\log n)^{L}$ (for some $L>1$ ), distinguish between the following with probability 0.9:

Completeness:: There exist $n/2$ vertices that cover at least $(1-\zeta)$ fraction of $E$ .
Soundness:: For every $S\subseteq V$ of size $n/2$ , there are at least $\delta\cdot|E|$ many edges which are not covered by any vertex in $S$ .

3.2 Plausibility of XXH: Three Possible Worlds

For the sake of the discussion in this subsection, we refer to the event “Clustering Barrier is Breached” to simply denote the existence of an algorithm much faster than $2^{k/\varepsilon}\cdot\mathrm{poly}(n)$ for $1+\varepsilon$ approximating the Euclidean $k$ -means problem. In Section 4, we proved that assuming XXH, the clustering barrier cannot be breached. Therefore, we are living in one of three possible worlds. The first world is where XXH is false and the clustering barrier is breached. The second world is where XXH is false, but the clustering barrier cannot be breached. Finally, the third world is where XXH is true (and thus the clustering barrier cannot be breached from Theorem 12).

The message we want to convey here is that only one of the above three worlds is possible, and regardless of which world is proven to be the one we live in, it will shed new light on problems of interest to the algorithmic community.

3.2.1 World I: XXH is False and Clustering Barrier is Breached

XXH may be viewed as a fine-grained assumption for the vertex cover problem on random instances, which we elaborate on below. Thus, our reduction from XXH instances to Euclidean $k$ -means instances, as given in Theorem 12, can be used to make oracle calls to the efficient algorithm for the Euclidean $k$ -means problem (since the clustering barrier is breached in this world) to solve XXH instances efficiently (i.e., in mildly sub-exponential time). This would imply a separation in this world between worst-case and average-case instances of the gap vertex cover problem (brushing aside many details to make a succinct claim).

XXH as a Fine-Grained Assumption for Random Instances.

Theorem 4.2 in [59] shows that for some large universal constant $C$ , a random $d$ -regular graph is a $(C,\frac{2}{d})$ -small set vertex expander with a probability of 0.5. Thus, making progress on the inapproximability of the vertex cover problem for vertex expanders is morally similar to proving the hardness of approximation for vertex cover on random $d$ -regular graphs. Or in this world, we would make algorithmic progress on understanding vertex cover on random graphs through (hypothetical) clustering algorithms.

3.2.2 World II: XXH is False but Clustering Barrier is not Breached

In this world, XXH is false, possibly because¹¹1We are not addressing here the concern that XXH might be false in this world because of the setting of the parameters. the vertex cover problem is computationally easy on small set vertex expanders. For spectral expanders, it is sometimes possible to apply Hoffman’s ratio bound [34] to obtain non-trivial speedups when the spectral gap is large. However, vertex expanders, while intuitively similar to edge expanders (and spectral ones), are poorly understood. In fact, explicit constructions with parameters close to those obtained for random graphs were developed only recently [36]. Thus, falsifying XXH motivates a better understanding of vertex expanders from the computational viewpoint of optimization problems.

Nevertheless, Theorem 11 in [2] shows that the exact vertex cover problem remains as hard on spectral expanders as it is on general graphs.

3.2.3 World III: XXH is True

The first evidence that XXH might be true is that the hard instances of vertex cover constructed by [27] are essentially built from random label cover instances which have strong expansion properties after PCP composition. Moreover, XXH only promises expansion for small sets (sub-polynomial size sets), and thus it is unlikely that such a local structure can be algorithmically used.

Also, it can be formally argued that on small sets, Ramanujan graphs are near-perfect vertex expanders [57]. Therefore, as a way to prove XXH, one can first ask whether the vertex cover problem admits a PTAS on Ramanujan graphs. It is possible that the answer to this question is negative, although there are no techniques to handle such questions, and thus XXH opens this new line of exploration.

3.3 Small Progress on XXH under Unique Games Conjecture

In this subsection, we show that without the vertex expansion property, it is possible to obtain a weak version of XXH under the unique games conjecture [44].

Let $\Phi$ denote the cumulative density function of the standard normal distribution and, for any $\rho\in[-1,1],\mu\in[0,1]$ , let $\Gamma_{\rho}(\mu)$ denote $\Pr[X\leq\Phi^{-1}(\mu)\wedge Y\leq\Phi^{-1}(\mu)]$ where $X, Y$ are normal random variables with means 0, variances 1 and covariance $\rho$ . The main intermediate result of [6] is the following:

Theorem 9 (Theorem 1 from [6]).

For any $q\in(0,1/2)$ and any $\varepsilon>0$ , it is UG-hard to, given a regular graph $G=(V,E)$ , distinguish between the following two cases.

$\blacksquare$

(Completeness) $G$ contains an independent set of size at least $q\cdot|V|$ .
$\blacksquare$

(Soundness) For any subset $T\subseteq V$ , the number of edges with both endpoint in $T$ is at least $|E|\cdot\left(\Gamma_{-q/(1-q)}(\mu)-\varepsilon\right)$ where $\mu=|T|/|V|$ .

This means that, in the completeness case, there is a vertex cover of size at most $(1-q)\cdot|V|$ . On the other hand, in the soundness case, if we consider any subset $S\subseteq V$ of size at most $(1-q)\cdot|V|$ , then the number of edges not covered is exactly the same as the number of edges with both endpoints in $(V\setminus S)$ , which is at least $(\Gamma_{-q/(1-q)}(q)-\varepsilon)\cdot|E|$ . We will evaluate this approximation factor for $q=\frac{1}{2}-\zeta$ .

Claim 10.

Let $q:=\frac{1}{2}-\zeta$ where $\zeta>0$ is small enough. We have: $\Gamma_{-q/(1-q)}(q)\geq\frac{\sqrt{\zeta}}{3}$ .

Assuming the above claim (which will be proved later), we have the following corollary from Theorem 9 by setting $\varepsilon\ll\sqrt{\zeta}$ :

Corollary 11.

There exists $\delta,\zeta>0$ with $\delta^{2}>\zeta/33$ such that it is UG-hard to, given a regular graph $G=(V,E)$ , distinguish between the following two cases.

Completeness:: There exist $|V|/2$ vertices that cover at least $(1-\zeta)$ fraction of $E$ .
Soundness:: For every $S\subseteq V$ of size $|V|/2$ , there are at least $\delta\cdot|E|$ many edges which are not covered by any vertex in $S$ .

This corollary is weaker than the promise given in XXH in the following ways. First, and most importantly, the hard instances of Corollary 11 need not be vertex expanders. Second, the conditional lower bound under the Unique Games Conjecture is only against polynomial-time algorithms, whereas XXH rules out sub-exponential time algorithms.

Between the two remarks made above, the first one is the major obstacle, and this is mainly to do with our state of poor understanding of vertex expanders. Once the toolkit develops on this topic, it is conceivable that some additional progress can be made on XXH.

4 Conditional Lower Bound for Euclidean $𝒌$ -means with Few Clusters

We prove in this section our main result, the hardness of approximating $k$ -means when parameterized by $k$ . The formal theorem is:

Theorem 12 (Fine-Grained Hardness for Approximation of Euclidean $k$ -means from XXH).

Suppose XXH $(\delta,\zeta,\alpha)$ is true for some constants $\delta,\zeta,\alpha\in(0,1)$ satisfying $\delta\leq 10^{-3}$ , $\zeta\leq\delta^{5}/10$ , and $\alpha\leq\delta^{10}$ . Let $L>1$ be the constant defining the degree $d=(\log|V|)^{L}$ in the XXH hypothesis.

Let $\widetilde{k}:\mathbb{N}\to\mathbb{N}$ be a non-decreasing function and $\widetilde{\varepsilon}:\mathbb{N}\to(0,1)$ be a non-increasing function. Define $f(n):=\frac{\widetilde{k}(n)}{\widetilde{\varepsilon}(n)}$ . Assume that for all sufficiently large $n$ , $f(n)$ satisfies the smoothness condition $f(n)\leq C\cdot f(n-1)$ for some constant $C\geq 1$ . Furthermore, assume the following asymptotic limits hold:

$\blacksquare$

$\widetilde{k}(1)\geq\frac{1}{\widetilde{\varepsilon}(1)}\geq 2/\delta^{5}$ .
$\blacksquare$

$f(n)=\omega(\log n)$ and $f(n)=o\left(\frac{n}{\log^{L}n}\right)$ .
$\blacksquare$

$\widetilde{\varepsilon}(n)=o\left(\frac{1}{(\log n)^{\omega(1)}}\right)$ .
$\blacksquare$

$\widetilde{k}(n)\cdot\widetilde{\varepsilon}(n)=\omega\left((\log n)^{2L}\right)$ .

Then the following holds for all $\beta>0$ : No randomized algorithm can, given as input exactly $n$ points in $\mathbb{R}^{\mathrm{poly}(n)}$ and an integer $\widetilde{k}(n)$ , run in $2^{f(n)^{1-\beta}}\cdot\mathrm{poly}(n)$ time and output a $(1+\widetilde{\varepsilon}(n))$ -approximate estimate of the $\widetilde{k}(n)$ -means cost with probability at least $0.9$ .

In this section, we actually prove the following theorem, which applies for $\widetilde{k}$ and $\widetilde{\varepsilon}$ bounded in a specific way and then show that it immediately implies Theorem 12 above.

Theorem 13.

Let $\delta,\zeta,\alpha\in(0,1)$ be some constants satisfying $\delta\leq 10^{-3}$ , $\zeta\leq\delta^{5}/10$ , and $\alpha\leq\delta^{10}$ . There is a randomized algorithm running in linear time in the input size, which takes as input an integer $k$ (where $k>\sqrt{|V|}\cdot d$ , $k=o(|V|/d^{\omega(1)})$ ) and a $d$ -regular $(\mathrm{polylog}|V|,\alpha)$ -small set vertex expander $G=(V,E)$ (where $d=(\log|V|)^{L}$ , for some $L>1$ ), and outputs a point-set $P\subseteq\mathbb{R}^{O(|V|)}$ of at most $|E|$ points such that with probability at least $0.95$ , the following holds:

Completeness:: If there are $|V|/2$ vertices covering at least $1-\zeta$ fraction of $E$ , then there is a clustering of $P$ such that the $k$ -means cost is at most $3|E|-(1-7\zeta)kd$ .
Soundness:: If every $|V|/2$ vertices miss at least $\delta$ fraction of $E$ , then every clustering of $P$ has $k$ -means cost at least $3|E|-(1-\delta^{5})kd$ .

$\blacktriangleright$ Remark 14.

It is worth noting that the reduction in Theorem 13 applies even for weaker versions of XXH. For example, if one day in the future, XXH was proved against algorithms running in time $2^{\sqrt{n}}$ instead of the currently stated $2^{n^{1-o(1)}}$ runtime algorithms, then we can recover that there is no randomized algorithm running in time much faster than $2^{\sqrt{k/\varepsilon}}\cdot\mathrm{poly}(n,d)$ that can $(1+\varepsilon)$ -approximate the Euclidean $k$ -means problem.

References

[1] Fateme Abbasi, Sandip Banerjee, Jaroslaw Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, Roohani Sharma, and Joachim Spoerhase. Parameterized approximation schemes for clustering with general norm objectives. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 1377–1399. IEEE, 2023. doi:10.1109/FOCS57990.2023.00085.
[2] Amir Abboud and Nathan Wallheimer. Worst-case to expander-case reductions. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA, volume 251 of LIPIcs, pages 1:1–1:23. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.ITCS.2023.1.
[3] Marek Adamczyk, Jaroslaw Byrka, Jan Marcinkowski, Syed Mohammad Meesum, and Michal Wlodarczyk. Constant-factor FPT approximation for capacitated k-median. In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, volume 144 of LIPIcs, pages 1:1–1:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ESA.2019.1.
[4] Pankaj K Agarwal and Cecilia Magdalena Procopiuc. Exact and approximation algorithms for clustering. Algorithmica, 33:201–226, 2002. doi:10.1007/S00453-001-0110-Y.
[5] Enver Aman, Karthik C. S., and Sharath Punna. On connections between k-coloring and euclidean k-means. In Timothy M. Chan, Johannes Fischer, John Iacono, and Grzegorz Herman, editors, 32nd Annual European Symposium on Algorithms, ESA 2024, September 2-4, 2024, Royal Holloway, London, United Kingdom, volume 308 of LIPIcs, pages 9:1–9:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.ESA.2024.9.
[6] Per Austrin, Subhash Khot, and Muli Safra. Inapproximability of vertex cover and independent set in bounded degree graphs. Theory of Computing, 7(1):27–43, 2011. doi:10.4086/TOC.2011.V007A003.
[7] Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, and Ali Kemal Sinop. The hardness of approximation of euclidean k-means. In Lars Arge and János Pach, editors, 31st International Symposium on Computational Geometry, SoCG 2015, June 22-25, 2015, Eindhoven, The Netherlands, volume 34 of LIPIcs, pages 754–767. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2015. doi:10.4230/LIPIcs.SOCG.2015.754.
[8] Mihai Badoiu, Sariel Har-Peled, and Piotr Indyk. Approximate clustering via core-sets. In John H. Reif, editor, Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 250–257. ACM, 2002. doi:10.1145/509907.509947.
[9] Anup Bhattacharya, Ragesh Jaiswal, and Amit Kumar. Faster algorithms for the constrained k-means problem. Theory Comput. Syst., 62(1):93–115, 2018. doi:10.1007/s00224-017-9820-7.
[10] Sujoy Bhore, Ameet Gadekar, and Tanmay Inamdar. Coreset strikes back: Improved parameterized approximation schemes for (constrained) k-median/means, 2025. doi:10.48550/arXiv.2504.06980.
[11] Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Xuan Wu. Coresets for clustering in excluded-minor graphs and beyond. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 2679–2696. SIAM, 2021. Consulted on arxiv on May 2022. doi:10.1137/1.9781611976465.159.
[12] Xianrun Chen, Lu Han, Dachuan Xu, Yicheng Xu, and Yong Zhang. k-median/means with outliers revisited: A simple fpt approximation. In Weili Wu and Guangmo Tong, editors, Computing and Combinatorics - 29th International Conference, COCOON 2023, Hawaii, HI, USA, December 15-17, 2023, Proceedings, Part II, volume 14423 of Lecture Notes in Computer Science, pages 295–302. Springer, 2023. doi:10.1007/978-3-031-49193-1_22.
[13] Rajesh Chitnis and Nitin Saurabh. Tight lower bounds for approximate & exact k-center in $\mathbb{r}$ ${}^{\mbox{d}}$ . In Xavier Goaoc and Michael Kerber, editors, 38th International Symposium on Computational Geometry, SoCG 2022, June 7-10, 2022, Berlin, Germany, volume 224 of LIPIcs, pages 28:1–28:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.SOCG.2022.28.
[14] Vincent Cohen-Addad, Arnaud de Mesmay, Eva Rotenberg, and Alan Roytman. The bane of low-dimensionality clustering. In Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2018. doi:10.1137/1.9781611975031.30.
[15] Vincent Cohen-Addad, Hossein Esfandiari, Vahab S. Mirrokni, and Shyam Narayanan. Improved approximations for euclidean k-means and k-median, via nested quasi-independent sets. In STOC ’22. ACM, 2022. doi:10.1145/3519935.3520011.
[16] Vincent Cohen-Addad, Andreas Emil Feldmann, and David Saulpic. Near-linear time approximation schemes for clustering in doubling metrics. J. ACM, 68(6):44:1–44:34, 2021. doi:10.1145/3477541.
[17] Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li. Tight FPT approximations for k-median and k-means. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 42:1–42:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ICALP.2019.42.
[18] Vincent Cohen-Addad and Karthik C. S. Inapproximability of clustering in lp metrics. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 519–539. IEEE Computer Society, 2019. doi:10.1109/FOCS.2019.00040.
[19] Vincent Cohen-Addad, Karthik C. S., and Euiwoong Lee. On approximability of clustering problems without candidate centers. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 2635–2648. SIAM, 2021. doi:10.1137/1.9781611976465.156.
[20] Vincent Cohen-Addad, Karthik C. S., and Euiwoong Lee. Johnson coverage hypothesis: Inapproximability of k-means and k-median in $\ell_{p}$ -metrics. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 1493–1530. SIAM, 2022. doi:10.1137/1.9781611977073.63.
[21] Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, and Chris Schwiegelshohn. Towards optimal lower bounds for k-median and k-means coresets. In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 1038–1051. ACM, 2022. doi:10.1145/3519935.3519946.
[22] Vincent Cohen-Addad and Jason Li. On the fixed-parameter tractability of capacitated clustering. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 41:1–41:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ICALP.2019.41.
[23] Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn. A new coreset framework for clustering. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 169–182. ACM, 2021. doi:10.1145/3406325.3451022.
[24] Sanjoy Dasgupta and Yoav Freund. Random projection trees for vector quantization. IEEE Transactions on Information Theory, 55(7):3229–3242, 2009. doi:10.1109/TIT.2009.2021326.
[25] Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, and Tom C. van der Zanden. A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs. SIAM J. Comput., 49(6):1291–1331, 2020. doi:10.1137/20M1320870.
[26] Irit Dinur. Mildly exponential reduction from gap 3sat to polynomial-gap label-cover. Electron. Colloquium Comput. Complex., TR16-128, 2016. URL: https://eccc.weizmann.ac.il/report/2016/128.
[27] Irit Dinur and Shmuel Safra. The importance of being biased. In John H. Reif, editor, Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 33–42. ACM, 2002. doi:10.1145/509907.509915.
[28] Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 569–578, 2011. doi:10.1145/1993636.1993712.
[29] Dan Feldman, Morteza Monemizadeh, and Christian Sohler. A PTAS for k-means clustering based on weak coresets. In Jeff Erickson, editor, Proceedings of the 23rd ACM Symposium on Computational Geometry, Gyeongju, South Korea, June 6-8, 2007, pages 11–18. ACM, 2007. doi:10.1145/1247069.1247072.
[30] Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, and Yuval Rabani. Approximation schemes for clustering problems. In Lawrence L. Larmore and Michel X. Goemans, editors, Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA, pages 50–58. ACM, 2003. doi:10.1145/780542.780550.
[31] Fedor V. Fomin, Petr A. Golovach, and Kirill Simonov. Parameterized k-clustering: Tractability island. J. Comput. Syst. Sci., 117:50–74, 2021. doi:10.1016/J.JCSS.2020.10.005.
[32] Sudipto Guha and Samir Khuller. Greedy strikes back: Improved facility location algorithms. J. Algorithms, 31(1):228–248, 1999. doi:10.1006/jagm.1998.0993.
[33] Venkatesan Guruswami and Piotr Indyk. Embeddings and non-approximability of geometric problems. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 12-14, 2003, Baltimore, Maryland, USA., pages 537–538, 2003. URL: http://dl.acm.org/citation.cfm?id=644108.644198.
[34] Willem H Haemers. Hoffman’s ratio bound. Linear Algebra and its Applications, 617:215–219, 2021.
[35] Lu Han, Dachuan Xu, Donglei Du, and Dongmei Zhang. An approximation algorithm for the uniform capacitated k-means problem. J. Comb. Optim., 44(3):1812–1823, 2022. doi:10.1007/S10878-020-00550-Y.
[36] Jun-Ting Hsieh, Alexander Lubotzky, Sidhanth Mohanty, Assaf Reiner, and Rachel Yun Zhang. Explicit lossless vertex expanders. In 66th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2025, Sydney, Australia. IEEE, 2025.
[37] Lingxiao Huang and Nisheeth K. Vishnoi. Coresets for clustering in euclidean spaces: importance sampling is nearly optimal. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 1416–1429. ACM, 2020. doi:10.1145/3357713.3384296.
[38] Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367–375, 2001. doi:10.1006/jcss.2000.1727.
[39] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512–530, 2001. doi:10.1006/jcss.2001.1774.
[40] Mary Inaba, Naoki Katoh, and Hiroshi Imai. Applications of weighted voronoi diagrams and randomization to variance-based k-clustering (extended abstract). In Proceedings of the Tenth Annual Symposium on Computational Geometry, Stony Brook, New York, USA, June 6-8, 1994, pages 332–339, 1994. doi:10.1145/177424.178042.
[41] Kamal Jain, Mohammad Mahdian, and Amin Saberi. A new greedy approach for facility location problems. In Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 731–740, 2002. doi:10.1145/509907.510012.
[42] Ragesh Jaiswal, Amit Kumar, and Sandeep Sen. A simple D 2-sampling based PTAS for k-means and other clustering problems. Algorithmica, 70(1):22–46, 2014. doi:10.1007/S00453-013-9833-9.
[43] Ragesh Jaiswal, Mehul Kumar, and Pulkit Yadav. Improved analysis of d2-sampling based ptas for k-means and other clustering problems. Information Processing Letters, 115(2):100–103, 2015. doi:10.1016/J.IPL.2014.07.009.
[44] Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 767–775, 2002. doi:10.1145/509907.510017.
[45] Sándor Kisfaludi-Bak, Jesper Nederlof, and Karol Wegrzycki. A gap-eth-tight approximation scheme for euclidean TSP. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 351–362. IEEE, 2021. doi:10.1109/FOCS52979.2021.00043.
[46] Amit Kumar, Yogish Sabharwal, and Sandeep Sen. Linear-time approximation schemes for clustering problems in any dimensions. J. ACM, 57(2), 2010. doi:10.1145/1667053.1667054.
[47] Kasper Green Larsen and Jelani Nelson. Optimality of the johnson-lindenstrauss lemma. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 633–638. IEEE Computer Society, 2017. doi:10.1109/FOCS.2017.64.
[48] Euiwoong Lee, Melanie Schmidt, and John Wright. Improved and simplified inapproximability for k-means. Inf. Process. Lett., 120:40–43, 2017. doi:10.1016/j.ipl.2016.11.009.
[49] Stuart Lloyd. Least squares quantization in pcm. IEEE transactions on information theory, 28(2):129–137, 1982. doi:10.1109/TIT.1982.1056489.
[50] Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Lower bounds based on the exponential time hypothesis. Bull. EATCS, 105:41–72, 2011. URL: http://eatcs.org/beatcs/index.php/beatcs/article/view/92.
[51] Meena Mahajan, Prajakta Nimbhorkar, and Kasturi R. Varadarajan. The planar k-means problem is np-hard. Theor. Comput. Sci., 442:13–21, 2012. doi:10.1016/J.TCS.2010.05.034.
[52] Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn. Performance of johnson-lindenstrauss transform for k-means and k-medians clustering. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 1027–1038, 2019. doi:10.1145/3313276.3316350.
[53] Pasin Manurangsi. A note on max k-vertex cover: Faster fpt-as, smaller approximate kernel and improved approximation. In Jeremy T. Fineman and Michael Mitzenmacher, editors, 2nd Symposium on Simplicity in Algorithms, SOSA 2019, January 8-9, 2019, San Diego, CA, USA, volume 69 of OASIcs, pages 15:1–15:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/OASIcs.SOSA.2019.15.
[54] Pasin Manurangsi. Tight running time lower bounds for strong inapproximability of maximum k-coverage, unique set cover and related problems (via t-wise agreement testing theorem). In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 62–81. SIAM, 2020. doi:10.1137/1.9781611975994.5.
[55] Pasin Manurangsi and Prasad Raghavendra. A birthday repetition theorem and complexity of approximating dense csps. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 78:1–78:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. doi:10.4230/LIPIcs.ICALP.2017.78.
[56] Dániel Marx. Parameterized complexity and approximation algorithms. Comput. J., 51(1):60–78, 2008. doi:10.1093/COMJNL/BXM048.
[57] Theo McKenzie and Sidhanth Mohanty. High-Girth Near-Ramanujan Graphs with Lossy Vertex Expansion. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pages 96:1–96:15, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2021.96.
[58] Nimrod Megiddo and Kenneth J Supowit. On the complexity of some common geometric location problems. SIAM journal on computing, 13(1):182–196, 1984. doi:10.1137/0213014.
[59] Salil P. Vadhan. Pseudorandomness. Found. Trends Theor. Comput. Sci., 7(1-3):1–336, 2012. doi:10.1561/0400000010.

[bib.bib1] [1] Fateme Abbasi, Sandip Banerjee, Jaroslaw Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, Roohani Sharma, and Joachim Spoerhase. Parameterized approximation schemes for clustering with general norm objectives. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 1377–1399. IEEE, 2023. doi:10.1109/FOCS57990.2023.00085.

[bib.bib2] [2] Amir Abboud and Nathan Wallheimer. Worst-case to expander-case reductions. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA, volume 251 of LIPIcs, pages 1:1–1:23. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.ITCS.2023.1.

[bib.bib3] [3] Marek Adamczyk, Jaroslaw Byrka, Jan Marcinkowski, Syed Mohammad Meesum, and Michal Wlodarczyk. Constant-factor FPT approximation for capacitated k-median. In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, volume 144 of LIPIcs, pages 1:1–1:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ESA.2019.1.

[bib.bib4] [4] Pankaj K Agarwal and Cecilia Magdalena Procopiuc. Exact and approximation algorithms for clustering. Algorithmica, 33:201–226, 2002. doi:10.1007/S00453-001-0110-Y.

[bib.bib5] [5] Enver Aman, Karthik C. S., and Sharath Punna. On connections between k-coloring and euclidean k-means. In Timothy M. Chan, Johannes Fischer, John Iacono, and Grzegorz Herman, editors, 32nd Annual European Symposium on Algorithms, ESA 2024, September 2-4, 2024, Royal Holloway, London, United Kingdom, volume 308 of LIPIcs, pages 9:1–9:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.ESA.2024.9.

[bib.bib6] [6] Per Austrin, Subhash Khot, and Muli Safra. Inapproximability of vertex cover and independent set in bounded degree graphs. Theory of Computing, 7(1):27–43, 2011. doi:10.4086/TOC.2011.V007A003.

[bib.bib7] [7] Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, and Ali Kemal Sinop. The hardness of approximation of euclidean k-means. In Lars Arge and János Pach, editors, 31st International Symposium on Computational Geometry, SoCG 2015, June 22-25, 2015, Eindhoven, The Netherlands, volume 34 of LIPIcs, pages 754–767. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2015. doi:10.4230/LIPIcs.SOCG.2015.754.

[bib.bib8] [8] Mihai Badoiu, Sariel Har-Peled, and Piotr Indyk. Approximate clustering via core-sets. In John H. Reif, editor, Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 250–257. ACM, 2002. doi:10.1145/509907.509947.

[bib.bib9] [9] Anup Bhattacharya, Ragesh Jaiswal, and Amit Kumar. Faster algorithms for the constrained k-means problem. Theory Comput. Syst., 62(1):93–115, 2018. doi:10.1007/s00224-017-9820-7.

[bib.bib10] [10] Sujoy Bhore, Ameet Gadekar, and Tanmay Inamdar. Coreset strikes back: Improved parameterized approximation schemes for (constrained) k-median/means, 2025. doi:10.48550/arXiv.2504.06980.

[bib.bib11] [11] Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Xuan Wu. Coresets for clustering in excluded-minor graphs and beyond. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 2679–2696. SIAM, 2021. Consulted on arxiv on May 2022. doi:10.1137/1.9781611976465.159.

[bib.bib12] [12] Xianrun Chen, Lu Han, Dachuan Xu, Yicheng Xu, and Yong Zhang. k-median/means with outliers revisited: A simple fpt approximation. In Weili Wu and Guangmo Tong, editors, Computing and Combinatorics - 29th International Conference, COCOON 2023, Hawaii, HI, USA, December 15-17, 2023, Proceedings, Part II, volume 14423 of Lecture Notes in Computer Science, pages 295–302. Springer, 2023. doi:10.1007/978-3-031-49193-1_22.

[bib.bib13] [13] Rajesh Chitnis and Nitin Saurabh. Tight lower bounds for approximate & exact k-center in $\mathbb{r}$ ${}^{\mbox{d}}$ . In Xavier Goaoc and Michael Kerber, editors, 38th International Symposium on Computational Geometry, SoCG 2022, June 7-10, 2022, Berlin, Germany, volume 224 of LIPIcs, pages 28:1–28:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.SOCG.2022.28.

[bib.bib14] [14] Vincent Cohen-Addad, Arnaud de Mesmay, Eva Rotenberg, and Alan Roytman. The bane of low-dimensionality clustering. In Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2018. doi:10.1137/1.9781611975031.30.

[bib.bib15] [15] Vincent Cohen-Addad, Hossein Esfandiari, Vahab S. Mirrokni, and Shyam Narayanan. Improved approximations for euclidean k-means and k-median, via nested quasi-independent sets. In STOC ’22. ACM, 2022. doi:10.1145/3519935.3520011.

[bib.bib16] [16] Vincent Cohen-Addad, Andreas Emil Feldmann, and David Saulpic. Near-linear time approximation schemes for clustering in doubling metrics. J. ACM, 68(6):44:1–44:34, 2021. doi:10.1145/3477541.

[bib.bib17] [17] Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li. Tight FPT approximations for k-median and k-means. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 42:1–42:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ICALP.2019.42.

[bib.bib18] [18] Vincent Cohen-Addad and Karthik C. S. Inapproximability of clustering in lp metrics. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 519–539. IEEE Computer Society, 2019. doi:10.1109/FOCS.2019.00040.

[bib.bib19] [19] Vincent Cohen-Addad, Karthik C. S., and Euiwoong Lee. On approximability of clustering problems without candidate centers. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 2635–2648. SIAM, 2021. doi:10.1137/1.9781611976465.156.

[bib.bib20] [20] Vincent Cohen-Addad, Karthik C. S., and Euiwoong Lee. Johnson coverage hypothesis: Inapproximability of k-means and k-median in $\ell_{p}$ -metrics. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 1493–1530. SIAM, 2022. doi:10.1137/1.9781611977073.63.

[bib.bib21] [21] Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, and Chris Schwiegelshohn. Towards optimal lower bounds for k-median and k-means coresets. In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 1038–1051. ACM, 2022. doi:10.1145/3519935.3519946.

[bib.bib22] [22] Vincent Cohen-Addad and Jason Li. On the fixed-parameter tractability of capacitated clustering. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 41:1–41:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ICALP.2019.41.

[bib.bib23] [23] Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn. A new coreset framework for clustering. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 169–182. ACM, 2021. doi:10.1145/3406325.3451022.

[bib.bib24] [24] Sanjoy Dasgupta and Yoav Freund. Random projection trees for vector quantization. IEEE Transactions on Information Theory, 55(7):3229–3242, 2009. doi:10.1109/TIT.2009.2021326.

[bib.bib25] [25] Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, and Tom C. van der Zanden. A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs. SIAM J. Comput., 49(6):1291–1331, 2020. doi:10.1137/20M1320870.

[bib.bib26] [26] Irit Dinur. Mildly exponential reduction from gap 3sat to polynomial-gap label-cover. Electron. Colloquium Comput. Complex., TR16-128, 2016. URL: https://eccc.weizmann.ac.il/report/2016/128.

[bib.bib27] [27] Irit Dinur and Shmuel Safra. The importance of being biased. In John H. Reif, editor, Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 33–42. ACM, 2002. doi:10.1145/509907.509915.

[bib.bib28] [28] Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 569–578, 2011. doi:10.1145/1993636.1993712.

[bib.bib29] [29] Dan Feldman, Morteza Monemizadeh, and Christian Sohler. A PTAS for k-means clustering based on weak coresets. In Jeff Erickson, editor, Proceedings of the 23rd ACM Symposium on Computational Geometry, Gyeongju, South Korea, June 6-8, 2007, pages 11–18. ACM, 2007. doi:10.1145/1247069.1247072.

[bib.bib30] [30] Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, and Yuval Rabani. Approximation schemes for clustering problems. In Lawrence L. Larmore and Michel X. Goemans, editors, Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA, pages 50–58. ACM, 2003. doi:10.1145/780542.780550.

[bib.bib31] [31] Fedor V. Fomin, Petr A. Golovach, and Kirill Simonov. Parameterized k-clustering: Tractability island. J. Comput. Syst. Sci., 117:50–74, 2021. doi:10.1016/J.JCSS.2020.10.005.

[bib.bib32] [32] Sudipto Guha and Samir Khuller. Greedy strikes back: Improved facility location algorithms. J. Algorithms, 31(1):228–248, 1999. doi:10.1006/jagm.1998.0993.

[bib.bib33] [33] Venkatesan Guruswami and Piotr Indyk. Embeddings and non-approximability of geometric problems. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 12-14, 2003, Baltimore, Maryland, USA., pages 537–538, 2003. URL: http://dl.acm.org/citation.cfm?id=644108.644198.

[bib.bib34] [34] Willem H Haemers. Hoffman’s ratio bound. Linear Algebra and its Applications, 617:215–219, 2021.

[bib.bib35] [35] Lu Han, Dachuan Xu, Donglei Du, and Dongmei Zhang. An approximation algorithm for the uniform capacitated k-means problem. J. Comb. Optim., 44(3):1812–1823, 2022. doi:10.1007/S10878-020-00550-Y.

[bib.bib36] [36] Jun-Ting Hsieh, Alexander Lubotzky, Sidhanth Mohanty, Assaf Reiner, and Rachel Yun Zhang. Explicit lossless vertex expanders. In 66th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2025, Sydney, Australia. IEEE, 2025.

[bib.bib37] [37] Lingxiao Huang and Nisheeth K. Vishnoi. Coresets for clustering in euclidean spaces: importance sampling is nearly optimal. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 1416–1429. ACM, 2020. doi:10.1145/3357713.3384296.

[bib.bib38] [38] Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367–375, 2001. doi:10.1006/jcss.2000.1727.

[bib.bib39] [39] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512–530, 2001. doi:10.1006/jcss.2001.1774.

[bib.bib40] [40] Mary Inaba, Naoki Katoh, and Hiroshi Imai. Applications of weighted voronoi diagrams and randomization to variance-based k-clustering (extended abstract). In Proceedings of the Tenth Annual Symposium on Computational Geometry, Stony Brook, New York, USA, June 6-8, 1994, pages 332–339, 1994. doi:10.1145/177424.178042.

[bib.bib41] [41] Kamal Jain, Mohammad Mahdian, and Amin Saberi. A new greedy approach for facility location problems. In Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 731–740, 2002. doi:10.1145/509907.510012.

[bib.bib42] [42] Ragesh Jaiswal, Amit Kumar, and Sandeep Sen. A simple D 2-sampling based PTAS for k-means and other clustering problems. Algorithmica, 70(1):22–46, 2014. doi:10.1007/S00453-013-9833-9.

[bib.bib43] [43] Ragesh Jaiswal, Mehul Kumar, and Pulkit Yadav. Improved analysis of d2-sampling based ptas for k-means and other clustering problems. Information Processing Letters, 115(2):100–103, 2015. doi:10.1016/J.IPL.2014.07.009.

[bib.bib44] [44] Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 767–775, 2002. doi:10.1145/509907.510017.

[bib.bib45] [45] Sándor Kisfaludi-Bak, Jesper Nederlof, and Karol Wegrzycki. A gap-eth-tight approximation scheme for euclidean TSP. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 351–362. IEEE, 2021. doi:10.1109/FOCS52979.2021.00043.

[bib.bib46] [46] Amit Kumar, Yogish Sabharwal, and Sandeep Sen. Linear-time approximation schemes for clustering problems in any dimensions. J. ACM, 57(2), 2010. doi:10.1145/1667053.1667054.

[bib.bib47] [47] Kasper Green Larsen and Jelani Nelson. Optimality of the johnson-lindenstrauss lemma. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 633–638. IEEE Computer Society, 2017. doi:10.1109/FOCS.2017.64.

[bib.bib48] [48] Euiwoong Lee, Melanie Schmidt, and John Wright. Improved and simplified inapproximability for k-means. Inf. Process. Lett., 120:40–43, 2017. doi:10.1016/j.ipl.2016.11.009.

[bib.bib49] [49] Stuart Lloyd. Least squares quantization in pcm. IEEE transactions on information theory, 28(2):129–137, 1982. doi:10.1109/TIT.1982.1056489.

[bib.bib50] [50] Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Lower bounds based on the exponential time hypothesis. Bull. EATCS, 105:41–72, 2011. URL: http://eatcs.org/beatcs/index.php/beatcs/article/view/92.

[bib.bib51] [51] Meena Mahajan, Prajakta Nimbhorkar, and Kasturi R. Varadarajan. The planar k-means problem is np-hard. Theor. Comput. Sci., 442:13–21, 2012. doi:10.1016/J.TCS.2010.05.034.

[bib.bib52] [52] Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn. Performance of johnson-lindenstrauss transform for k-means and k-medians clustering. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 1027–1038, 2019. doi:10.1145/3313276.3316350.

[bib.bib53] [53] Pasin Manurangsi. A note on max k-vertex cover: Faster fpt-as, smaller approximate kernel and improved approximation. In Jeremy T. Fineman and Michael Mitzenmacher, editors, 2nd Symposium on Simplicity in Algorithms, SOSA 2019, January 8-9, 2019, San Diego, CA, USA, volume 69 of OASIcs, pages 15:1–15:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/OASIcs.SOSA.2019.15.

[bib.bib54] [54] Pasin Manurangsi. Tight running time lower bounds for strong inapproximability of maximum k-coverage, unique set cover and related problems (via t-wise agreement testing theorem). In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 62–81. SIAM, 2020. doi:10.1137/1.9781611975994.5.

[bib.bib55] [55] Pasin Manurangsi and Prasad Raghavendra. A birthday repetition theorem and complexity of approximating dense csps. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 78:1–78:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. doi:10.4230/LIPIcs.ICALP.2017.78.

[bib.bib56] [56] Dániel Marx. Parameterized complexity and approximation algorithms. Comput. J., 51(1):60–78, 2008. doi:10.1093/COMJNL/BXM048.

[bib.bib57] [57] Theo McKenzie and Sidhanth Mohanty. High-Girth Near-Ramanujan Graphs with Lossy Vertex Expansion. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pages 96:1–96:15, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2021.96.

[bib.bib58] [58] Nimrod Megiddo and Kenneth J Supowit. On the complexity of some common geometric location problems. SIAM journal on computing, 13(1):182–196, 1984. doi:10.1137/0213014.

[bib.bib59] [59] Salil P. Vadhan. Pseudorandomness. Found. Trends Theor. Comput. Sci., 7(1-3):1–336, 2012. doi:10.1561/0400000010.

Near-Optimal Bounds for Parameterized Euclidean k-Means

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Question 1.

1.1 Our Results

Theorem 2 (Answer to Question 1; informal statement).

Corollary 3.

1.2 Further Related Work

Hardness of Clustering.

FPT algorithms via Sketching.

From Continuous to Discrete Clustering.

Approximation Algorithms in Euclidean Spaces.

2 Our Techniques

2.1 Motivation and Technical Background

Current Understanding of the Landscape.

Exploring Uncharted Territories.

Technical Challenges.

A (Failed) Simple Approach.

Embedding via Color Coding.

Need for Vertex Expansion.

2.2 New Hypothesis: Exponential Time for Expanders Hypothesis

Exponential Time for Expanders Hypothesis (XXH).

Plausibility of XXH.

Our Message.

2.3 Proof Overview of Theorem 2

Lemma 4 (Informal statement).

Lemma 5 (Informal statement).

Lemma 6 (Informal statement).

3 Exponential Time for Expanders Hypothesis

3.1 New Hypothesis: Exponential Time for Expanders Hypothesis

Definition 7 (Small Set Vertex Expanders).

Hypothesis 8 (Exponential Time for Expanders Hypothesis – XXH(δ,ζ,α)).

3.2 Plausibility of XXH: Three Possible Worlds

3.2.1 World I: XXH is False and Clustering Barrier is Breached

XXH as a Fine-Grained Assumption for Random Instances.

3.2.2 World II: XXH is False but Clustering Barrier is not Breached

3.2.3 World III: XXH is True

3.3 Small Progress on XXH under Unique Games Conjecture

Theorem 9 (Theorem 1 from [6]).

Claim 10.

Corollary 11.

4 Conditional Lower Bound for Euclidean 𝒌-means with Few Clusters

Theorem 12 (Fine-Grained Hardness for Approximation of Euclidean k-means from XXH).

Theorem 13.

▶ Remark 14.

References

Hypothesis 8 (Exponential Time for Expanders Hypothesis – XXH $(\delta,\zeta,\alpha)$ ).

4 Conditional Lower Bound for Euclidean $𝒌$ -means with Few Clusters

Theorem 12 (Fine-Grained Hardness for Approximation of Euclidean $k$ -means from XXH).

$\blacktriangleright$ Remark 14.