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 k-means++ seeding algorithm is one of the most popular algorithms that isused for finding the initial $k$ centers when using the k-means heuristic. Thealgorithm is a simple sampling procedure and can be described as follows: Pickthe first center randomly from the given points. For $i > 1$, pick a point tobe the $i^{th}$ center with probability proportional to the square of theEuclidean distance of this point to the closest previously $(i-1)$ chosencenters.  The k-means++ seeding algorithm is not only simple and fast but also gives an$O(\log{k})$ approximation in expectation as shown by Arthur and Vassilvitskii.There are datasets on which this seeding algorithm gives an approximationfactor of $\Omega(\log{k})$ in expectation. However, it is not clear from theseresults if the algorithm achieves good approximation factor with reasonablyhigh probability (say $1/poly(k)$). Brunsch and R\"{o}glin gave a dataset wherethe k-means++ seeding algorithm achieves an $O(\log{k})$ approximation ratiowith probability that is exponentially small in $k$. However, this and allother known lower-bound examples are high dimensional. So, an open problem wasto understand the behavior of the algorithm on low dimensional datasets. Inthis work, we give a simple two dimensional dataset on which the seedingalgorithm achieves an $O(\log{k})$ approximation ratio with probabilityexponentially small in $k$. This solves open problems posed by Mahajan et al.and by Brunsch and R\"{o}glin.

A tight lower bound instance for k-means++ in constant dimension