English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The Euclidean $k$-means problem is a classical problem that has beenextensively studied in the theoretical computer science, machine learning andthe computational geometry communities. In this problem, we are given a set of$n$ points in Euclidean space $R^d$, and the goal is to choose $k$ centers in$R^d$ so that the sum of squared distances of each point to its nearest centeris minimized. The best approximation algorithms for this problem include apolynomial time constant factor approximation for general $k$ and a$(1+\epsilon)$-approximation which runs in time $poly(n) 2^{O(k/\epsilon)}$. Atthe other extreme, the only known computational complexity result for thisproblem is NP-hardness [ADHP'09]. The main difficulty in obtaining hardnessresults stems from the Euclidean nature of the problem, and the fact that anypoint in $R^d$ can be a potential center. This gap in understanding left openthe intriguing possibility that the problem might admit a PTAS for all $k,d$.  In this paper we provide the first hardness of approximation for theEuclidean $k$-means problem. Concretely, we show that there exists a constant$\epsilon > 0$ such that it is NP-hard to approximate the $k$-means objectiveto within a factor of $(1+\epsilon)$. We show this via an efficient reductionfrom the vertex cover problem on triangle-free graphs: given a triangle-freegraph, the goal is to choose the fewest number of vertices which are incidenton all the edges. Additionally, we give a proof that the current best hardnessresults for vertex cover can be carried over to triangle-free graphs. To showthis we transform $G$, a known hard vertex cover instance, by taking a graphproduct with a suitably chosen graph $H$, and showing that the size of the(normalized) maximum independent set is almost exactly preserved in the productgraph using a spectral analysis, which might be of independent interest.

The Hardness of Approximation of Euclidean k-means