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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Given a set of points , the -means clustering problem is to find a set of   , such that the objective function ∑ (,), where (,) denotes the Euclidean distance between  and the closest center in , is minimized. This is one of the most prominent objective functions that has been studied with respect to clustering.  -sampling (Arthur and Vassilvitskii, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA’07, pp. 1027–1035, SIAM, Philadelphia, ) is a simple non-uniform sampling technique for choosing points from a set of points. It works as follows: given a set of points , the first point is chosen uniformly at random from . Subsequently, a point from  is chosen as the next sample with probability proportional to the square of the distance of this point to the nearest previously sampled point.  -sampling has been shown to have nice properties with respect to the -means clustering problem. Arthur and Vassilvitskii (Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA’07, pp. 1027–1035, SIAM, Philadelphia, ) show that  points chosen as centers from  using  -sampling give an (log) approximation in expectation. Ailon et al. (NIPS, pp. 10–18, ) and Aggarwal et al. (Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp. 15–28, Springer, Berlin, ) extended results of Arthur and Vassilvitskii (Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA’07, pp. 1027–1035, SIAM, Philadelphia, ) to show that () points chosen as centers using  -sampling give an (1) approximation to the -means objective function with high probability. In this paper, we further demonstrate the power of  -sampling by giving a simple randomized (1+)-approximation algorithm that uses the  -sampling in its core.

A Simple D 2-Sampling Based PTAS for k-Means and Other Clustering Problems