CS Paper Radar

Tight Bounds on the Cost of Adaptivity for the Meyerson Sketch

Edith Cohen, Elena Gribelyuk, Pasin Manurangsi, Uri Stemmer

cs.DS ·submitted 2026-09-06 15:21 UTC · v1

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))$.

Closest papers

Nearest neighbours by meaning across the whole index.

Metric Facility Location under Batched Random Order

cs.DS ·2026-11-03 ·Fabrizio Grandoni, Stefano Leonardi, Matteo Russo
theory similarity 0.68
Abstract

We study online metric facility location in the batched random-order model. An adversary partitions $n$ clients into $B$ nonempty batches, which arrive in uniformly random order. Each batch is revealed in full, and its clients must be connected to open facilities before the next batch arrives. Openings and assignments are irrevocable, and the objective is to minimize the total opening and connection cost. For both uniform and nonuniform opening costs, we prove that the tight competitive ratio is \[ Θ\!\left(\min\left\{\log(B+1), \sqrt{\log(n-B+2)}\right\}\right). \] Thus, the ratio is constant both when there is a single batch and when every batch is a singleton, but intermediate numbers of batches can require a $Θ(\sqrt{\log n})$ ratio. Our algorithms build on Meyerson's algorithm (2001) and do not need to know $n$ nor $B$. A key algorithmic novelty is that we process the clients in a batch one by one in uniform random order (hence neglecting the global properties of the batch). We present a novel analysis of this algorithm that hinges on the random order of the batches, as well as of the clients within each batch. We also provide a matching competitive ratio lower bound already for uniform costs, and even when the entire metric is known in advance.

0.21

List Update with Time Windows and Delays without Batch-Serving

cs.DS ·2026-11-12 ·Icey Siyi Ai, Jingwei Li, Clifford Stein
theory similarity 0.66
Abstract

We study list update with time windows and delays when every request requires a separate access. Unlike batch-serving models, serving several requests to one element still incurs one access per request, and each access may change the list for subsequent requests. For time windows of overlap at most $k\ge2$, our deterministic First-Element Removal algorithm is $(3-2/k)$-competitive, hence $3$-competitive in general. Against an oblivious adversary, a randomized adaptation of BIT is $7/4$-competitive on arbitrary $2$-overlap inputs. More generally, on inputs without self-overlap, it is $\left(13/4-9/[2(k+1)]\right)$-competitive for every $k\ge2$. For delays, we give a deterministic $5$-competitive algorithm and a lower bound of $2+\sqrt3$ for deterministic delay-unaware algorithms. Our analyses extend inversion potentials with per-request credits that reconcile different service times and orders.

0.21

Online Algorithms with a Sample: Tight Bounds and Adversarial Robustness

cs.DS ·2026-09-18 ·Anish Hebbar, Ravi Kumar, Roie Levin, Joseph, Naor +1 more
similarity 0.65
Abstract

Suppose an online algorithm is given an unbiased $p$-sample of its input as offline advice; can the algorithm exploit the sample to achieve beyond-worst-case performance? We study this online algorithms with a sample (OAS) model. We show a tight $O\left(\log (1/p) \cdot \log m + \log n\right)$-competitive algorithm for set cover, exponentially improving upon the $O\left(1/p \cdot \log (mn)\right)$ guarantee of Gupta et al. (SODA'24) and answering an open question therein. Our techniques extend to covering integer programs and non-metric facility location, also yielding tight bounds for these problems. Further, we give an $O(\log (1/p)/ \log \log (1/p))$-competitive algorithm for metric facility location, answering an open question of Argue et al. (NeurIPS'22). We then introduce and study the robust variant of the OAS model, in which an adversary is allowed to arbitrarily modify $k$ elements of the $p$-sample. For set cover, covering integer programs, and non-metric facility location, we obtain a tight competitive ratio of $O\left(\log (k/p) \cdot \log m + \log n\right)$. For metric facility location and Steiner tree, we obtain tight competitive ratios of $O\left(\log (k/p) / \log \log (k/p) \right)$ and $O\left(\log (k/p)\right)$ respectively. To the best of our knowledge, these are the first results for robust algorithms in the OAS setting.

0.19

Paging with Per-Replacement Maximum Delay

cs.DS ·2026-08-26 ·Tianhang Lu, Runtian Ren, Shengcai Liu
theoryhot direction similarity 0.64
Abstract

Classical paging serves every miss immediately. We study paging with per-replacement maximum delay, where loading a pending page costs one movement plus the age of its oldest outstanding request and clears that page's entire episode. Equivalently, the holding rate is the number of pending pages. For cache size $k$, threshold LRU is strictly $(5k+3)$-competitive, while a randomized algorithm is strictly $5H_k$-competitive against an oblivious adversary; classical constructions give matching $Ω(k)$ and $Ω(H_k)$ orders. Offline, we obtain an exact $O(nk)$ dynamic program with one hole, an exact configuration algorithm for any fixed number of holes, and a nonproactive polynomial-time $5$-approximation in general. Physical farthest-next-use can nevertheless fail with only three pages. For page-dependent fetch costs with spread $ρ=w_{\max}/w_{\min}$, the exact fixed-number-of-holes algorithms persist. We obtain a $(3ρ+2)$-approximation and online guarantees with multiplicative factors $O(ρk)$ deterministically and $O(ρH_k)$ randomly against an oblivious adversary, plus any additive term inherited from the corresponding classical guarantee. A strict $Ω(\sqrtρ)$ randomized lower bound already holds for one cache slot. Thus maximum delay preserves the unit-cost competitive hierarchy but disrupts classical offline structure and makes weighted timing spread-sensitive.

0.30

Improved Randomized Approximations for Strategic Obnoxious Facility Location

cs.GT ·2026-09-07 ·Hau Chan, Jianan Lin, Chenhao Wang
publishedtheory similarity 0.62
Abstract · To appear in ISAAC 2026

We study randomized strategyproof mechanisms for strategic obnoxious facility location on a line segment, where agents wish the facility to be located as far away from them as possible and their utility is their distance from the facility, under the social utility and minimum utility objectives. For social utility, we propose a novel randomized mechanism that breaks the previously best known \(\frac32\)-approximation of [Cheng, Yu, and Zhang, TCS 2013], achieving an approximation ratio of at most \(1.47359\). We also raise the lower bound on the approximation ratio of randomized strategyproof mechanisms from \(\frac{2}{\sqrt{3}}\approx1.15470\) [Feigenbaum et al., JAAMAS 2020] to \(\frac{105}{88}\approx1.19318\). For minimum utility, following the profile-independent approach of [Chan, Lin and Wang, AAMAS 2026], we design a simple randomized mechanism that reduces the approximation guarantee from \(\sqrt{2n}+O(1)\) to \(\sqrt n+O(1)\), where \(n\) is the number of agents. Finally, we prove that no randomized strategyproof mechanism can achieve an asymptotic approximation ratio strictly smaller than \(2\), strengthening the previous asymptotic lower bound of \(\frac32\) [Feigenbaum et al., JAAMAS 2020]. Thus, all four bounds considered in this paper strictly improve upon the corresponding previously known results.

0.30

Optimal High Probability Bounds for Random Order Online Sorting

cs.DS ·2026-10-11 ·Chenglin Fan, Mingyu Kang
theory similarity 0.62
Abstract · 46 pages

In random order online sorting, a fixed multiset of $n$ real numbers arrives in a uniformly random order. Each value must be placed immediately and irrevocably into an empty position of an array with exactly $n$ positions. The objective is to minimize the sum of the absolute differences between consecutive entries. If the entire input were known in advance, sorting the values would be optimal and would have cost equal to the range of the input. We prove that the optimal worst case competitive ratio in this model is $Θ(\log n)$ with high probability. In particular, we give a single online algorithm that achieves an $O(\log n)$ competitive ratio with high probability for every fixed input, and we show that every randomized online algorithm has some fixed input on which an $Ω(\log n)$ ratio is unavoidable with high probability. The same upper bound also holds for independent samples from an arbitrary unknown distribution on the real line. The algorithm uses the random arrival order to learn the relative positions of future values from the values seen so far. It maintains a hierarchy of small regions of the input order and allows an arriving value to use nearby space when its preferred region is full. This flexibility avoids the need to reserve large amounts of space for unlikely local fluctuations. The analysis shows that large displacements become rapidly less likely as their scale grows, leading to the $O(\log n)$ high probability bound. A matching lower bound shows that no randomized online algorithm can improve the logarithmic dependence in the worst case.

0.23

Optimizing Both Checking and Update Costs in Random Walk Search

cs.DS cs.CCcs.DMmath.PR ·2026-09-16 ·Simon Apers, Marin Costes
theory similarity 0.62
Abstract

Random walks are a standard tool for search problems in which a state can be updated locally and tested for being marked. When updating the state and checking whether it is marked have different costs, two classical strategies optimize different parts of the cost: checking after every step is optimal in the number of updates, while repeatedly checking only after mixing is optimal in the number of checks. For a single marked state $m$ and a walk started from its stationary distribution $π$, Dohotaru and Høyer stated that both guarantees can be matched simultaneously, for a walk that checks after blocks of a fixed length; their argument is sketched through quantum walks, and they observe that they know of no classical proof. We give a short and self-contained classical proof of such a tradeoff, for arbitrary irreducible Markov chains. The algorithm replaces the original transition matrix $P$ by the averaged walk $ \overline P_τ= \frac{1}τ\sum_{k=1}^τ P^k, $ where $τ$ is of order $π(m)HT(m)$. Using a coupling with the original walk and Kac's lemma, we prove directly that the averaged walk hits the marked state in $O(1/π(m))$ checks in expectation. The resulting search cost is \[ S + O(HT(m))U + O(1/π(m))C \] in expectation, where $S$, $U$, and $C$ denote setup, update, and checking costs.

0.19

Randomized Algorithm for MMS Allocation of Chores with Online Agent Arrivals

cs.GT ·2026-10-11 ·Haolong Li, Fangxiao Wang, Xiaowei Wu
similarity 0.62
Abstract

We study the fair allocation of $m$ indivisible chores among $n$ agents in the agent-arrival model against an oblivious adversary. The chore set and the number of agents are known in advance. When agent $i$ arrives, her nonnegative additive cost function $c_i$ is revealed, and the algorithm must immediately and irrevocably assign her a subset of the unallocated chores. We focus on the notion of maximin share (MMS) and measure the fairness of the realized allocation $X$ by the ex-post MMS approximation ratio $ρ(X)$. We measure an algorithm's performance by its expected ratio, and also the guarantees that hold with high probability. For binary additive costs, we achieve an expected ex-post MMS ratio of $3/2+o(1)$, and show that every randomized online algorithm has an expected ratio of at least $3/2-o(1)$. For every $n$, the expected ratio is at most $1.755$. A variant of our algorithm guarantees an approximation ratio of $2$ with high probability, which is optimal. % For general additive costs, we present a weighted-rounding algorithm that achieves an expected ratio of $2+o(1)$, which also holds with high probability. The expected ratio is at most $2.594$ for every $n$. We also show that similar algorithms extend to additive goods, achieving a constant expected ex-post MMS ratio and guaranteeing every agent an $x$-fraction of her MMS with probability at least $1-85x^2$ for every $x\le1/15$.

0.39