arXiv preprint ·
Tight Bounds on the Cost of Adaptivity for the Meyerson Sketch
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
In online facility location, points arrive one at a time, and the algorithm must either open a facility at the arriving point or route the point to an existing facility. The Meyerson sketch opens a facility at each arriving point with probability proportional to the point's distance to the closest open facility, and requires no state beyond the set of open centers. Due to its simplicity, space efficiency, and strong guarantees against the offline optimum, the Meyerson sketch has become a workhorse of streaming and online clustering. In many such applications, however, the set of open facilities are visible to the process that generates the stream, which can adaptively select future points based on the algorithm's past random choices, voiding its classical guarantees. In this work, we quantify the effect of such adaptivity. We compare an adaptively generated run of the sketch against an \emph{oblivious replay}, an independent execution, with fresh coins, on the very same generated sequence, and study the \emph{adaptivity ratio} of expected adaptive cost to expected replay cost. We determine the worst-case ratio in both directions: adaptivity can neither inflate nor deflate the expected cost, or the number of open facilities, by more than an $O(\logΔ/\log\logΔ)$ factor, where $Δ$ is the aspect ratio of the input points (the ratio of the largest to the smallest pairwise distance). This is asymptotically tight as there are deterministic generators on the real line that inflate or deflate the cost by an $Ω(\logΔ/\log\logΔ)$ factor. We show that these robustness guarantees carry over to Meyerson-based sketches for approximate $k$ clustering with sketch size $O(k\,\mathrm{polylog}(n))$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
1.73-Optimal Echelon Stock (R,nQ) Policies in Two-Stage Stochastic Serial Systems
Accelerated High-Accuracy Sampling from a Warm Start via the Proximal Bouncy Particle Sampler
Query-Oblivious Coresets for Softmax Attention: Improved Bounds and Efficient Constructions
Smoothed Picard Hamiltonian Monte Carlo
Computation and Applications of Euclidean and Normed Representations of Massive Data
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.