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

We study k-median clustering under the sequential no-substitution setting. Inthis setting, a data stream is sequentially observed, and some of the pointsare selected by the algorithm as cluster centers. However, a point can beselected as a center only immediately after it is observed, before observingthe next point. In addition, a selected center cannot be substituted later. Wegive the first algorithm for this setting that obtains a constant approximationfactor on the optimal risk under a random arrival order, an exponentialimprovement over previous work. This is also the first constant approximationguarantee that holds without any structural assumptions on the input data.Moreover, the number of selected centers is only quasi-linear in k. Ouralgorithm and analysis are based on a careful risk estimation that avoidsoutliers, a new concept of a linear bin division, and a multiscale approach tocenter selection.

A Constant Approximation Algorithm for Sequential Random-Order No-Substitution k-Median Clustering