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/

Zendy Plus

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

Zendy Tools

Zendy Open

The most well known and ubiquitous clustering problem encountered in nearlyevery branch of science is undoubtedly $k$-means: given a set of data pointsand a parameter $k$, select $k$ centres and partition the data points into $k$clusters around these centres so that the sum of squares of distances of thepoints to their cluster centre is minimized. Typically these data points lie$\mathbb{R}^d$ for some $d\geq 2$.  $k$-means and the first algorithms for it were introduced in the 1950's.Since then, hundreds of papers have studied this problem and many algorithmshave been proposed for it. The most commonly used algorithm is known asLloyd-Forgy, which is also referred to as "the" $k$-means algorithm, andvarious extensions of it often work very well in practice. However, they mayproduce solutions whose cost is arbitrarily large compared to the optimumsolution. Kanungo et al. [2004] analyzed a simple local search heuristic to geta polynomial-time algorithm with approximation ratio $9+\epsilon$ for any fixed$\epsilon>0$ for $k$-means in Euclidean space.  Finding an algorithm with a better approximation guarantee has remained oneof the biggest open questions in this area, in particular whether one can get atrue PTAS for fixed dimension Euclidean space. We settle this problem byshowing that a simple local search algorithm provides a PTAS for $k$-means in$\mathbb{R}^d$ for any fixed $d$. More precisely, for any error parameter$\epsilon>0$, the local search algorithm that considers swaps of up to$\rho=d^{O(d)}\cdot{\epsilon}^{-O(d/\epsilon)}$ centres at a time finds asolution using exactly $k$ centres whose cost is at most a$(1+\epsilon)$-factor greater than the optimum.  Finally, we provide the first demonstration that local search yields a PTASfor the uncapacitated facility location problem and $k$-median with non-uniformopening costs in doubling metrics.

Local Search Yields a PTAS for k-Means in Doubling Metrics