The Hardness of Approximation of Euclidean k-means

Introduction

While the $k$-means heuristic is very much tied to the $k$-means objective function, there are many examples where it converges to a solution which is far away from the optimal $k$-means solution. This raises the important question of whether there exist provable algorithms for the $k$-means problem in general Euclidean space, which is the focus problem of our paper. Unfortunately though, the approximability of the problem is not very well understood. From the algorithmic side, there has been much focus on getting $(1+\epsilon)$-approximations that run as efficiently as possible. Indeed, for fixed $k$, Euclidean $k$-means admits a PTAS . These algorithms have exponential dependence in $k$, but only linear dependence in the number of points and the dimensionality of the space. As mentioned above, there is also empirical and theoretical evidence for the effectiveness of very simple heuristics for this problem . For arbitrary $k$ and $d$, the best known approximation algorithm for $k$-means achieves a factor of $9+\epsilon$ . In contrast to the above body of work on getting algorithms for $k$-means, lower bounds for $k$-means have remained elusive. In fact, until recently, even NP-hardness was not known for the $k$-means objective . This is perhaps due to the fact that as opposed to many discrete optimization problems, the $k$-means problem allows one to choose any point in the Euclidean space as a center. The above observations lead to the following intriguing possibility

Is there a PTAS for Euclidean $k$-means for arbitrary $k$ and dimension $d$?

In this paper we answer this question in the negative and provide the first hardness of approximation for the Euclidean $k$-means problem.

There exists a constant $\epsilon>0$ such that it is NP-hard to approximate the Euclidean $k$-means to a factor better than $(1+\epsilon)$.

The starting point for our reduction is the Vertex-Cover problem on triangle-free graphs: here, given a triangle-free graph, the goal is to choose the fewest number of vertices which are incident on all the edges in the graph. This naturally leads us to our other main result in this paper, that of showing hardness of approximation of vertex cover on triangle-free graphs. Kortsarz et al show that if the vertex cover problem is hard to approximate to a factor of $\alpha\geq 3/2$, then it is hard to approximate vertex cover on triangle-free graphs to the same factor of $\alpha$. While such a hardness (in fact, a factor of $2-\epsilon$ ) is known assuming the stronger unique games conjecture, the best known NP-hardness results do not satisfy $\alpha\geq 3/2$. We settle this question by showing NP-hardness results for approximating vertex cover on triangle-free graphs, which match the best known hardness on general graphs.

It is NP-hard to approximate Vertex Cover on triangle-free graphs to within any factor smaller than $1.36$.

Main Technical Contribution

In Section 4, we show a reduction from Vertex-Cover on triangle-free graphs to Euclidean $k$-means where the vertex cover instances have small cover size if and only if the corresponding $k$-means instances have a low cost. A crucial ingredient is to relate the cost of the clusters to the structural properties of the original graph, which lets us transition from the Euclidean problem to a completely combinatorial problem. Then in Section 5, we prove that the known hardness of approximation results for Vertex-Cover carry over to triangle-free graphs. This improves over existing hardness results for vertex cover on triangle-free graphs . Furthermore, we believe that our proof techniques are of independent interest. Specifically, our reduction transforms known hard instances $G$ of vertex cover, by taking a graph product with an appropriately chosen graph $H$. We then show that the size of the vertex cover in the new graph (in proportion to the size of the graph) can be related to spectral properties of $H$. In fact, by choosing $H$ to have a bounded spectral radius, we show that the vertex covers in $G$ and the product graph are roughly preserved, while also ensuring that the product graph is triangle-free. Combining this with our reduction to $k$-means completes the proof.

Related Work

Arthur and Vassilvitskii proposed $k$-means++, a random sampling based approximation algorithm for Euclidean $k$-means which achieves a factor of $O(\log k)$. This was improved by Kanungo et al. who proposed a local search based algorithm which achieves a factor of $(9+\epsilon)$. This is currently the best known approximation algorithm for $k$-means. For fixed $k$ and $d$, Matousek gave a PTAS for $k$-means which runs in time $O(n\epsilon^{-2k^{2}d}\log^{k}n))$. Here $n$ is the number of points and $m$ is the dimensionality of the space. This was improved by Badoiu et al. who gave a PTAS for fixed $k$ and any $d$ with run time $O(2^{({k/\epsilon})^{O(1)}}poly(d)n\log^{k}n)$. Kumar et al. gave an improved PTAS with exponential dependence in $k$ and only linear dependence in $n$ and $d$. Feldman et al. combined this with efficient coreset constructions to give a PTAS for fixed $k$ with improved dependence on $k$. The work of Dasgupta and Aloise et al. showed that Euclidean $k$-means is NP-hard even for $k=2$. Mahajan et al. also show that the $k$-means problem is NP-hard for points in the plane.

There are also many other clustering objectives related to $k$-means which are commonly studied. The most relevant to our discussion are the $k$-median and the $k$-center objectives. In the first problem, the objective is to pick $k$ centers to minimize the sum of distances of each point to the nearest center (note that the distances are not squared). The problem deviates from $k$-means in two crucial aspects, both owing to the different contexts in which the two problems are studied: (i) the $k$-median problem is typically studied in the setting where the centers are one of the data points (or come from a set of possible centers specified in the input), and (ii) the problem is also very widely studied on general metrics, without the Euclidean restriction. The $k$-median problem has been a testbed of developing new techniques in approximation algorithms, and has constantly seen improvements even until very recently . Currently, the best known approximation for $k$-median is a factor of $2.611+\epsilon$ due to Bykra et al. . On the other hand, it is also known that the $k$-median objective (on general metrics) is NP-hard to approximate to a factor better than $(1+1/e)$ . When restricted to Euclidean metrics, Kolliopoulos et al. show a PTAS for $k$-median on constant dimensional spaces. On the negative side for $k$-median on Euclidean metrics, it is known that the discrete problem (where centers come from a specified input) cannot have a PTAS under standard complexity assumptions . As mentioned earlier, all these results are for the version when the possible candidate centers is specified in the input. For the problem where any point can be a center, Arora et al. show a PTAS when the points are on a 2-dimensional plane.

In the $k$-center problem the objective is to pick $k$ center points such that the maximum distance of any data point to the closest center point is minimized. In general metrics, this problem admits a $2$-factor approximation which is also optimal assuming $P\neq NP$ . For Euclidean metric when the center could be any point in the space, the upper bound is still $2$ and the best hardness of approximation is a factor $1.82$ .

Our Hardness Reduction: From Vertex Cover to Euclidean k𝑘k-means

In this section, we show a reduction from the Vertex-Cover problem (on triangle-free graphs) to the $k$-means problem. Formally, the vertex cover problem can be stated as follows: Given an undirected graph $G=(V,E)$, choose a subset $S$ of vertices (with minimum $|S|$) such that $S$ is incident on every edge of the graph. More specifically, our reduction establishes the following theorem.

There is an efficient reduction from instances of Vertex Cover (on triangle-free graphs) to those of Euclidean $k$-means that satisfies the following properties:

if the Vertex Cover instance has value $k$, then the $k$-means instance has cost at most $m-k$.

if the Vertex Cover instance has value at least $k(1+\epsilon)$, then the optimal $k$-means cost is at least $m-(1-\Omega(\epsilon))k$. Here, $\epsilon$ is some fixed constant $>0$.

In 5, we show that there exist triangle-free graph instances of vertex cover on $m=\Theta(n)$ edges, and $k=\Omega(n)$ such that it is NP-hard to distinguish if the instance has a vertex cover of size at most $k$, or all vertex covers have size at least $(1+\epsilon)k$, for some constant $\epsilon>0$.

Now, let $k=m/\Delta$ where $\Delta=\Omega(1)$ from the hard vertex cover instances. Then, from 3, we get that if the vertex cover has value $k$, then the $k$-means cost is at most $m(1-\frac{1}{\Delta})$, and if the vertex cover is at least $k(1+\epsilon)$, then the optimal $k$-means cost is at least $m(1-\frac{1-\Omega(\epsilon)}{\Delta})$. Therefore, the vertex cover hardness says that it is also NP-hard to distinguish if the resulting $k$-means instance has cost at most $m(1-\frac{1}{\Delta})$ or cost more than $m(1-\frac{1-\Omega(\epsilon)}{\Delta})$. Since $\Delta$ is a constant, this implies that it is NP-hard to approximate the $k$-means problem within some factor $(1+\Omega(\epsilon))$, thereby establishing our main result 1. In what follows, we prove 3.

Let $G=(V,E)$ denote the graph in the Vertex Cover instance ${\cal I}$, with parameter $k$ denoting the number of vertices we can select. We associate the vertices with natural numbers $[n]$. Therefore, we refer to vertices by natural numbers $i$, and edges by pairs of natural numbers $(i,j)$.

As stated, the dimensionality of the points we have constructed is $n$, and we get a hardness factor of $(1+\epsilon)$. However, by using the dimensionality reduction ideas of Johnson and Lindenstrauss (see, e.g. ), without loss of generality, we can assume that the points lie in $O(\log n/\epsilon^{2})$ dimensions and our hardness results still hold true. This is because, after the transformation, all pairwise distances (and in particular, the $k$-means objective function) are preserved upto a factor of $(1+\epsilon/10)$ of the original values, and so our hardness factor is also (almost) preserved, i.e., we would get hardness of approximation of $(1+\Omega(\epsilon))$.

However, for simplicity, we stick with the $n$ dimensional vectors as it makes the presentation much cleaner.

2 Completeness

Given any clustering $\{\mathcal{F}\}$, the following hold.

$\sum_{\mathcal{F}}d_{\mathcal{F}}(i)=d_{G}(i)$.

$\sum_{i}\sum_{\mathcal{F}}d_{\mathcal{F}}(i)=2m=2|E|$.

The proof is immediate, because every edge $e\in E$ belongs to exactly one cluster in $\{\mathcal{F}\}$. ∎

Our next claim relates the connection cost of any cluster $\mathcal{F}$ to the structure of the associated subgraph, which forms the crucial part of the analysis.

The total connection cost of any cluster $\mathcal{F}$ is:

Firstly, note that $\sum_{i}d_{\mathcal{F}}(i)=2m_{\mathcal{F}}$. Now consider the center $\mu_{\mathcal{F}}$ of cluster $\mathcal{F}$. By definition, we have that at coordinate $i\in V$:

So $\|\mu_{\mathcal{F}}\|^{2}=\frac{1}{m^{2}}\sum_{i}d_{\mathcal{F}}(i)^{2}$. Hence the total cost of this clustering is:

There exists a clustering of our $k$-means instance ${\cal I}_{km}$ with cost at most $m-k$, where $m$ is the number of edges in the graph $G=(V,E)$ associated with the vertex cover instance ${\cal I}$, and $k$ is the size of the optimal vertex cover.

Consider a cluster $\mathcal{F}_{v}$, which consists of data points associated with edges covered by a single vertex $v$. Then, by 6, the connection cost of this cluster is precisely $m_{\mathcal{F}_{v}}-1$, since the sub-graph associated with a cluster is simply a star rooted at $v$. Here, $m_{\mathcal{F}_{v}}$ is the number of edges which $v$ covers in the vertex cover (if an edge is covered by different vertices in the cover, it is included in only one vertex). Then, summing over all clusters, we get the claim. ∎

3 Soundness

In this section, we show that if there is a clustering of low $k$-means cost, then there is a very good vertex cover for the corresponding graph. We begin with some useful notation.

Given a set $E^{\prime}\subseteq\binom{V}{2}$ of $m_{E^{\prime}}=|E^{\prime}|$ edges with corresponding node degrees $(d_{1},\ldots,d_{n})$, we define $\mathsf{Cost}(E^{\prime})$ as the following:

Note that, by 6, the connection cost of a clustering $\Gamma=\{\mathcal{F}_{1},\mathcal{F}_{2},\ldots,\mathcal{F}_{k}\}$ of the $n$ points is equal to $\sum_{i}\mathsf{Cost}(\mathcal{F}_{i})$. Recall that we abuse notation slightly and view each cluster $\mathcal{F}_{i}$ of the data points also as a subset of $E$. Moreover, because $\Gamma$ clusters all points, the subgraphs $\mathcal{F}_{1},\mathcal{F}_{2},\ldots,\mathcal{F}_{k}$ form a partition of $E$. Using this analogy, we study the properties of each subgraph and show that if the $k$-means cost of $\Gamma$ is small, then most of these subgraphs in fact are stars. This will in turn help us recover a small vertex cover for $G$. We begin with a simple property of $\mathsf{Cost}(E^{\prime})$.

For any set of $m_{E^{\prime}}$ edges $E^{\prime}$, $m_{E^{\prime}}-1\leq\mathsf{Cost}(E^{\prime})\leq 2m_{E^{\prime}}-1.$

We have \mathsf{Cost}(E^{\prime})=\sum_{u\in V}d_{u}\Big{(}1-\frac{d_{u}}{m_{E^{\prime}}}\Big{)}=2m_{E^{\prime}}-\frac{\sum_{u\in V}d^{2}_{u}}{m_{E^{\prime}}}. The proof follows from noting that $\frac{\sum_{u\in V}d^{2}_{u}}{m_{E^{\prime}}}\geq\frac{\sum_{u\in V}d_{u}}{m_{E^{\prime}}}=2$ and $\frac{\sum_{u\in V}d^{2}_{u}}{m_{E^{\prime}}}\leq m_{E^{\prime}}+1$. The last inequality is due to the fact that $\sum_{u\in V}d^{2}_{u}$ is maximized by the degree sequence $(m_{E^{\prime}},1,1,\ldots,1)$. ∎

If the $k$-means instance ${\cal I}_{km}$ has a clustering $\Gamma=\{\mathcal{F}_{1},\ldots,\mathcal{F}_{k}\}$ with $\sum_{\mathcal{F}\in\Gamma}\mathsf{Cost}(\mathcal{F})\leq m-(1-\delta)k$, then there exists a $(1+O(\delta))k$-vertex cover of $G$ in the instance ${\cal I}$.

Note that this, along with 7 would complete the proof of 3.

This means, except $\leq 2\delta k$ clusters, the remaining clusters all have $\delta_{i}\leq\frac{1}{2}$. Moreover, 11 implies all these $(1-2\delta)k$ clusters are either stars or triangles and have $\delta_{i}=0$. Since the graph is triangle free, they are all stars, and hence the corresponding center vertices cover all the edges in the respective clusters. It now remains to cover the edges in the remaining $2\delta k$ clusters which have larger $\delta_{i}$ values. Indeed, even for these clusters, we can appeal to 11, and choose two vertices per cluster to cover all but $\delta_{i}$ edges in each cluster. So the size of our candidate vertex cover is at most $k(1+2\delta)$, and we have covered all but $\sum_{i}\delta_{i}$ edges. But now, we notice that $\sum_{i}\delta_{i}\leq\delta k$, and so we can simply include one vertex per uncovered edge and would obtain a vertex cover of size at most $k(1+3\delta)$, thus completing the proof. ∎

Given a graph $G_{\mathcal{F}}=(V,\mathcal{F})$ with $m=|\mathcal{F}|$ edges and degrees $(d_{1},\ldots,d_{n})$; let $\delta$ be such that

There always exists an edge $\{u,v\}\in\mathcal{F}$ with $d_{u}+d_{v}-1\geq m+1+\delta$. Furthermore, if $\delta<\frac{1}{2}$, then $\delta=0$ and $G_{\mathcal{F}}$ is either a star graph or a triangle.

Since $\sum_{u}{d_{u}}^{2}=\sum_{u\sim v}(d_{u}+d_{v})$, we can think of $\frac{1}{m}\sum_{u}{d_{u}}^{2}$ as the the expectation of $d_{u}+d_{v}$ over a random edge chosen uniformly, $\{u,v\}\in E$:

From this, we can immediately conclude the existence of an edge $\{u,v\}$ with $d_{u}+d_{v}\geq m+1-\delta$. Now to complete the second part of the Lemma statement, suppose $d_{u}\geq d_{v}$. The number of edges incident to $\{u,v\}$ is:

Since $\sum_{u}d_{u}^{2}$ is Schur-convex, its value increases under majorization:

So we obtain $2\alpha(\beta-1)\leq(\alpha+\beta-1)\delta+4(\beta-1)$. Since $\beta\geq 2$, we divide both sides by $\beta-1$:

In particular, $(2-\delta)\alpha\leq 4+\delta\implies\alpha\leq\frac{4+\delta}{2-\delta}<3$ as $\delta<1/2$. Hence $\alpha\leq 2$. Consequently, $d_{u}=d_{v}=2$ and $m=d_{u}+d_{v}-1=3$. There are two possible cases: The graph is either a $3$-cycle or $4$-path. In the latter case, the corresponding $\delta$ is:

which is a contradiction and the graph is a triangle. ∎

Putting the pieces together, we get the proof of 3.

Unique Games Hardness: Khot and Regev show that approximating Vertex-Cover to factor $(2-\epsilon)$ is hard assuming the Unique Games conjecture. Furthermore, Kortsarz et al. show that any approximation algorithm with ratio $\alpha\geq 1.5$ for Vertex-Cover on $3$-cycle-free graphs implies an $\alpha$ approximation algorithm for Vertex-Cover (on general graphs). This result combined with the reduction in this section immediately implies APX hardness for $k$-means under the unique games conjecture. In the next section we generalize the result of Kortsarz et al. by giving an approximation preserving reduction from Vertex-Cover on general graphs to Vertex-Cover on triangle-free graphs. This would enable us to get APX hardness for the $k$-means problem.

Hardness of Vertex Cover on Triangle-Free Graphs

In this section, we show that the Vertex Cover problem is as hard on triangle-free graphs as it is on general graphs. To this end, for any graph $G=(V,E)$, we define $\operatorname{IS}(G)$ as the size of maximum independent set in $G$. For convenience, we define $\operatorname{rel-IS}(G)$ as the ratio of $\operatorname{IS}(G)$ to the number of nodes in $G$:

Similarly, let $\operatorname{VC}(G)$ be the size of minimum vertex cover in $G$ and $\operatorname{rel-VC}(G)$ be the ratio $\frac{\operatorname{VC}(G)}{|V|}$. The following is well known, which says independent sets and vertex covers are duals of each other.

Given $G=(V,E)$, $I\subseteq V$ is an independent set if and only if $C=V\setminus I$ is a vertex cover. In particular, $\operatorname{IS}(G)+\operatorname{VC}(G)=|V|$.

Combining 14 with the best known unconditional hardness result for Vertex Cover, due to Dinur and Safra , we obtain the following corollary.

Given any unweighted triangle-free graph $G$ with bounded degrees, it is NP-hard to approximate Vertex Cover within any factor smaller than $1.36$.

Given two simple graphs $G=(V_{1},E_{1})$ and $H=(V_{2},H_{2})$, we define the Kronecker product of $G$ and $H$, $G\otimes H$, as the graph with nodes $V(G\otimes H)=V_{1}\times V_{2}$ and edges:

Observe that, if $A_{G}$ and $A_{H}$ denote the adjacency matrix of $G$ and $H$, then $A_{G\otimes H}=A_{G}\otimes A_{H}$.

Given any symmetric matrix $M$, we will use $\sigma_{i}(M)$ to denote the $i^{th}$ largest eigenvalue of $M$. For any graph $G$ on $n$-nodes, we define the spectral radius of $G$, $\rho(G)$, as the following:

Here $\mathbf{e}$ is the all $1$’s vector of length $n$.

If $H$ is triangle-free, then so does $G\otimes H$.

Suppose $G\otimes H$ has a $3$-cycle of the form $((a,i),(b,j),(c,k),(a,i))$. Then $(i,j,k,i)$ is a closed walk in $H$. $H$ is triangle-free, therefore $i=j$ wlog; a contradiction as $H$ has no loops. ∎

The following Lemma says that as long as $H$ has good spectral properties, the relative size of maximum independent sets in $G$ will be preserved by $G\otimes H$.

Suppose $H$ is a $d$-regular graph with spectral radius $\leq\rho$. For any graph $G$ with maximum degree $\Delta$,

For the lower bound, consider an independent set $I$ in $G$. It is easy to check that $I\times[N]$ is an independent set in $G\otimes H$, thus $\operatorname{IS}(G\otimes H)\geq N\cdot\operatorname{IS}(G)\implies\operatorname{rel-IS}(G\otimes H)\geq\operatorname{rel-IS}(G)$.

For the upper bound, consider the indicator vector $f\in\{0,1\}^{[n]\times[N]}$ of an independent set in $G\otimes H$. Since the corresponding set contains no edges from $G\otimes H$,

Define $p\in^{V}$ as the following vector:

For each $u\in[n]$, pick $u$ with probability $p_{u}$. Let $I_{0}\subseteq[n]$ be the set of picked nodes. Next, start with $I\leftarrow I_{0}$. As long as there is an edge of $G$ contained in ${I}$, arbitrarily remove one of its endpoints from $I$. At the end of this process, the remaining set $I$ is an independent set for $G$, and its size is at least the size of $I_{0}$ minus the number of edges contained in $I_{0}$. Hence ${}{|I|}\geq{}{|I_{0}|-|E_{G}(I_{0},I_{0})|}.$ Observe that

The probability of any pair $i\neq j$ being contained in $I_{0}$ is given by

In the remaining part, we prove the supporting claims.

$p^{T}Ap=\frac{1}{N}{f}^{T}(A\otimes\widetilde{J_{N}})f$ where $\widetilde{J_{N}}$ is the $N$-by-$N$ matrix of all $1/N$’s.

The second-to-last identity follows from the bi-linearity of Kronecker product. ∎

$f^{T}(A\otimes\widetilde{J_{N}})f\leq|f^{T}A\otimes(B-\widetilde{J_{N}})f|$.

We have f^{T}(A\otimes\widetilde{J_{N}})f=f^{T}\Big{[}A\otimes\big{(}\widetilde{J_{N}}-B)\Big{]}f+f^{T}(A\otimes B)f. As noted above, $f$ being an independent set implies $f^{T}(A\otimes B)f=0$:

$|f^{T}A\otimes(B-\widetilde{J_{N}})f|\leq\frac{\Delta\rho}{d}\|f\|^{2}$.

We know that the spectrum of the Kronecker product of two symmetric matrices correspond to the pairwise product of the spectrum of corresponding matrices, i.e., all eigenvalues of $A\otimes C$ are of the form $\sigma_{i}(A)\cdot\sigma_{j}(C)$ for each $i$ and $j$. Therefore,

Observe that $\rho(A)\leq\Delta$, since $A$ is the adjacency matrix of a graph with degree $\leq\Delta$. Now we will upper bound $\rho(C)$. Since $H$ is a regular graph and $B$ is its normalized adjacency matrix, the largest eigenvector of $B$ is all $1$’s and the corresponding eigenvalue is $1$. Therefore $C$ has the same eigenspace with $B$. Moreover $C\mathbf{e}=0$, thus:

We now prove the main theorem needed for our reduction.

Given a graph $G=(V,E)$ with maximum degree $\Delta$, for any $\varepsilon>0$, we can construct in polynomial time, a triangle-free graph $\widehat{G}=(\widehat{V},\widehat{E})$ with

$d_{\max}(G\otimes H)\leq d_{\max}(G)\times d_{\max}(H)\leq O(\Delta d)=O(\Delta^{3}\varepsilon^{-2})$. ∎

Noga Alon has provided an alternate construction where one can obtain a triangle free graph $\hat{G}$ such that $\operatorname{rel-IS}(\hat{G})=\operatorname{rel-IS}(G)$. This however, does not lead to improved constant in our analysis. For the sake of completeness, we include the alternate theorem in the Appendix (See Theorem 24).

We will end the section with the proof of 15. We need the following hardness result of : It follows from their Corollary 2.3 and Appendix 8 (weighted to unweighted reduction). As noted in , the construction produces bounded degree graphs.

For any constant $\varepsilon>0$, given any unweighted graph $G$ with bounded degrees, it is NP-hard to distinguish between:

(Yes) $\operatorname{rel-IS}(G)>c-\varepsilon$,

(No) $\operatorname{rel-IS}(G)<s+\varepsilon$;

where $c$ and $s$ are constants such that $\frac{1-s}{1-c}\approx 1.36$.

Given a bounded degree graph $G$, consider the graph $\widehat{G}$ given by 21 for some small constant $\varepsilon_{0}<\varepsilon$. Since $G$ is bounded degree and $\varepsilon_{0}$ is constant, $\widehat{G}$ is also bounded degree. Furthermore, $\widehat{G}$ satisfies $\operatorname{rel-IS}(G)\leq\operatorname{rel-IS}(\widehat{G})\leq(1+\varepsilon_{0})\operatorname{rel-IS}(G)$. Completeness follows immediately: $\operatorname{rel-IS}(\widehat{G})>c-\varepsilon$. For the soundness, suppose $\operatorname{rel-IS}(\widehat{G})>s+\varepsilon$. Then $\operatorname{rel-IS}(G)\geq\frac{s+\varepsilon}{1+\varepsilon_{0}}\geq s+\varepsilon$ for suitable $\varepsilon_{0}$. The hardness of Vertex Cover follows from 13. ∎

Conclusions

In this paper we provide the first hardness of approximation for the fundamental Euclidean $k$-means problem. Although our work clears a major hurdle of going beyond NP-hardness for this problem, there is still a big gap in our understanding with the best upper bound being a factor $(9+\epsilon)$. We believe that our result and techniques will pave way for further work in closing this gap. Our reduction from vertex cover produces high dimensional instances ($d=\Omega(n)$) of $k$-means. However, by using the Johnson-Lindenstrauss transform , we can project the instance onto $O(\log n/\epsilon^{2})$ dimensions and still preserve pairwise distances by a factor $(1+\epsilon)$ and the $k$-means cost by a factor of $(1+\epsilon)^{2}$. We leave it as an open question to investigate inapproximability results for $k$-means in constant dimensions. It would also be interesting to study whether our techniques give hardness of approximation results for the Euclidean $k$-median problem. Finally, our hardness reduction in 5 provides a novel analysis by using the spectral properties of the underlying graph to argue about independent sets in graph products – this connection could have applications beyond the present paper.

Acknowledgments

We would like to thank Noga Alon and Oded Regev for valuable feedback on the results in 5, in particular for suggesting alternate proofs of Theorem 16 and Theorem 17. We would also like to thank Noga for pointing out that the graph product construction in 5 does not eliminate even cycles.

References

Appendix A Appendix

Let $G=(V,E)$ be an arbitrary graph with maximum degree $\Delta$. It is possible to construct in polynomial time a triangle free graph $\hat{G}$ such that $\operatorname{rel-IS}(\hat{G})=\operatorname{rel-IS}(G)$.

Before proving the theorem, we need the following standard facts about $(n,d,\lambda)$ graphs. The following proofs are suggested by Noga Alon.

Let $H=(U,F)$ be an $(n,d,\lambda)$ graph, assume $\lambda<d/4$ and let $B$ be a set of vertices of $H$. Let $N(B)$ denote the set of all neighbors of $B$ in $H$. Then:

If $|B|>\frac{\lambda}{d}n$ then $|N(B)|>n-\frac{\lambda}{d}n$

If $|B|\leq\frac{\lambda}{d}n$ then $|N(B)|\geq\frac{\lambda}{2d}n$

Part $1$ is proved in Corollary $1$ in . Part $2$, for $\frac{2\lambda^{2}}{d^{2}}n\leq|B|\leq\frac{\lambda}{d}n$ follows from the same corollary (which implies that in this range $|N(B)|\geq\frac{n}{2}$). For $|B|\leq\frac{2\lambda^{2}}{d^{2}}n$, the result follows from the expander mixing lemma (see , corollary $9.2.5$), as there are $d|B|$ edges between $B$ and $N(B)$. ∎

Let $H=(U,F)$ be a $(n,d,\lambda)$-expander with $\lambda\leq 2\sqrt{d-1}$This means that all eigenvalues of $H$, except the first, are bounded by $lambda$. Let $\hat{G}=G\otimes H$. Further, let $\frac{d}{2\lambda}\geq\Delta$. It is well known that such graphs exist. It is easy to see that any $\operatorname{rel-IS}(G\otimes H)\geq\operatorname{rel-IS}(G)$, since any independent set $S$ in $G$ leads to an independent set $S\otimes U$ in $G\otimes H$.

For the other direction, let $S\subset V\times U$ be an independent set in $G\otimes H$. Define

Be Lemma 25 part $1$, $T$ is an independent set in $G$. Let $T^{\prime}$ be a maximal (with respect to containment) independent set in $G$ that contains $T$. By maximality, every vertex in $V\setminus T^{\prime}$ has at least one neighbor in $T^{\prime}$. Thus $T^{\prime}$ is a dominating set in $G$ and there is a collection of stars $\{S_{v}:v\in T^{\prime}\}$, covering all the vertices of $G$. As $T^{\prime}$ is an independent set, $|T^{\prime}|\leq\operatorname{rel-IS}(G)|V|$. To complete the proof it suffices to show that for each of the stars $S_{v}$ in our collection whose set of vertices in $G$ is $V_{v}$

The number of leaves of the star $S_{v}$ is at most $\Delta$. For each such leaf $v^{\prime}$, the set of vertices of $H$ given by

is of cardinality smaller than $\frac{\lambda}{d}n$. Moreover, all its neighbors in $H$ cannot belong to the set $B_{v}=\{u\in U:(v,u)\in S\}$ where $v$ is the center of the star $S_{v}$. By Lemma 25 part $2$, the number of these neighbors is at least $\frac{d}{2\lambda}\geq\Delta$ times the cardinality of $B_{v^{\prime}}$. This implies that the total size of all sets $B_{v^{\prime}}$ where the sum ranges over all leaves $v^{\prime}$ of $S_{v}$ is at most the number of vertices in $U-B_{v}$, implying 1 and completing the proof. ∎