A streaming algorithm for 2-center with outliers in high dimensions (Q680151)

From MaRDI portal
Revision as of 23:42, 14 July 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
A streaming algorithm for 2-center with outliers in high dimensions
scientific article

    Statements

    A streaming algorithm for 2-center with outliers in high dimensions (English)
    0 references
    0 references
    0 references
    22 January 2018
    0 references
    Let \(P\) be a finite collection of points in \(d\)-dimensional Euclidean space. In the \textit{2-center problem,} one is to find two balls of minimal but equal radii that contain all of \(P\). In the outliers variant of the problem, one allows some points from \(P\) to lie outside of the two balls. Under the streaming input data assumption, where only a single pass over the set \(P\) is allowed, the authors present and establish the correctness of an approximation algorithm for solving the 2-center problem with outliers. Specifically, the algorithm produces two equal-sized balls that contain all but at most \(z\) points from \(P\) and with radius that is within a factor of \(1.8+\epsilon\) of the optimal radius. It has a \(O(d^3z^2+dz^4/\epsilon)\) space requirement, and an update time that is polynomial in \(d\), \(z\), \(1/\epsilon\) (an explicit expression is not given).
    0 references
    0 references
    \(k\)-center
    0 references
    outlier
    0 references
    high dimensions
    0 references
    data stream
    0 references

    Identifiers