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 $k$-center problem for a point set~$P$ asks for a collection of $k$congruent balls (that is, balls of equal radius) that together cover all thepoints in $P$ and whose radius is minimized. The $k$-center problem withoutliers is defined similarly, except that $z$ of the points in $P$ do need notto be covered, for a given parameter $z$. We study the $k$-center problem withoutliers in data streams in the sliding-window model. In this model we aregiven a possibly infinite stream $P=\langle p_1,p_2,p_3,\ldots\rangle$ ofpoints and a time window of length $W$, and we want to maintain a small sketchof the set $P(t)$ of points currently in the window such that using the sketchwe can approximately solve the problem on $P(t)$.  We present the first algorithm for the $k$-center problem with outliers inthe sliding-window model. The algorithm works for the case where the pointscome from a space of bounded doubling dimension and it maintains a set $S(t)$such that an optimal solution on $S(t)$ gives a $(1+\varepsilon)$-approximatesolution on $P(t)$. The algorithm is deterministic and uses$O((kz/\varepsilon^d)\log \sigma)$ storage, where $d$ is the doubling dimensionof the underlying space and $\sigma$ is the spread of the points in the stream.Algorithms providing a $(1+\varepsilon)$-approximation were not even known inthe setting without outliers or in the insertion-only setting with outliers. Wealso present a lower bound showing that any algorithm that provides a$(1+\varepsilon)$-approximation must use $\Omega((kz/\varepsilon)\log \sigma)$storage.

$k$-Center Clustering with Outliers in the Sliding-Window Model