CS Paper Radar

Optimal High Probability Bounds for Random Order Online Sorting

Chenglin Fan, Mingyu Kang

cs.DS ·submitted 2026-10-11 08:24 UTC · v1
theory

Abstract

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.

Comment
46 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Online and Fully-Dynamic Sorting

cs.DS ·2026-11-16 ·Yossi Azar, Sujoy Bhore, Devdan Dey, Debmalya Panigrahi, Or Vardi +1 more
theory similarity 0.76
Abstract

Online sorting asks how to place $n$ sequentially arriving elements in an array to minimize the sum of absolute differences between consecutive elements. Fully-dynamic sorting further extends the problem to allow both element insertions and deletions. Without recourse, these problems face strong lower bounds on the competitive ratio: $Ω(\sqrt{n})$ for online sorting and $Ω(n)$ for fully-dynamic sorting. In sharp contrast, we show that allowing only poly-logarithmic recourse yields at least exponential improvements in the competitive ratio for both problems:(1) Our main algorithmic result is a deterministic fully-dynamic sorting algorithm that is $O(\log^2 n)$-competitive and has $O(\log^4 n)$ amortized recourse per update. We complement this with a lower bound showing that any deterministic algorithm with any $O(\mathrm{polylog}(n))$ competitive ratio has amortized recourse at least $Ω(\sqrt{\log n})$.(2) For the insertion-only setting, we establish a family of approximation--recourse tradeoffs, including $O(\log\log n)$ competitive ratio with $O(\log\log n)$ amortized recourse. Given the lower bound in the fully-dynamic case, this result shows that the insertion-only problem yields exponentially better bounds than the fully-dynamic one.(3) Finally, we show that the stronger approximation-recourse tradeoff for the insertion-only case extends to the fully-dynamic setting when the array has $(1+\varepsilon)n$ space.

0.09

Building On Learning-Augmented Online Sorting

cs.DS ·2026-10-29 ·Wyatt Olson
similarity 0.73
Abstract · 5 pages, 0 figures

Online sorting is a problem that has gained attention recently, and is a natural translation of sorting into an online setting. The problem at hand is to place elements of an online sequence immediately and irrevocably with the goal of producing an array that is as close to sorted as possible upon inserting all elements. Recent work by Bercea et al. [ESA 2026] introduced the incorporation of learned predictions into the online sorting domain. They show lower bounds for the consistency and robustness of any algorithm, including randomization, then provide a deterministic algorithm that is $O(n/r)$-consistent and $O(r)$-robust, which are tight bounds. However, this algorithm requires prior knowledge of the optimal offline cost of the full input sequence before all elements have been revealed. We resolve this by providing an algorithm with matching bounds that does not require knowledge of the optimal cost, then extend these results to the more general problem of online metric TSP, in line with the prior work.

0.14

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.72
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

Online Fair Division: Pushing the Frontier of Approximate Proportionality

cs.GT ·2026-09-12 ·Yingjian Du, Ankang Sun
theoryhighly cited similarity 0.67
Abstract · In this updated version, we add a discussion of an independent work that studies related results. We also add a new section that presents a …

Online fair division captures allocation problems in which indivisible resources arrive over time and must be assigned before future resources are known. Understanding what fairness remains achievable when allocation decisions are immediate and irrevocable is a fundamental question in this setting. We study deterministic online allocation among $n$ agents with nonnegative additive valuations, where the number of goods is unknown and the adversary can adapt to previous allocation decisions. We focus on proportionality up to one good (PROP1) and examine how advance information affects the achievable guarantees. Without additional future information, we give a deterministic algorithm that guarantees $Ω(\frac{1}{\log(nm)})$-PROP1 after every round, where $m$ is the number of goods at termination. We complement this result by showing that, for every $n$ and sufficiently large $m$, every deterministic algorithm has an adaptive instance with $m$ goods on which its allocation has PROP1 approximation guarantee $O(\frac{\log \log m}{\log m})$. Thus, when the number of agents is fixed, our upper and lower bounds on the competitive ratio differ by at most an $O(\log\log m)$ factor. These results answer an open question proposed by Choo et al. on whether a nontrivial deterministic approximation for PROP1 can be obtained. We also study the setting where the algorithm knows the predictions of the maximum item value for every agent. When the predictions are accurate, we give a deterministic $\frac{1}{2}$-PROP1 algorithm, improving the $\frac{1}{n}$ guarantee of Choo et al. to a constant. We further establish an explicit upper bound below one on the competitive ratio, even for two agents with accurate predictions. Finally, we give a single deterministic algorithm that guarantees $\frac{1}{2}$-PROP1 when predictions are accurate and $Ω(\frac{1}{\log (nm)})$-PROP1 for arbitrary predictions.

0.40

Online Allocation using Few Samples

cs.DS cs.GT ·2026-09-15 ·Matthew Faw, Sahil Singla, Yifan Wang
similarity 0.66
Abstract

We study online allocation problems where $n$ requests over $m$ resources arrive in an adversarial order and must be served immediately and irrevocably. This framework captures both Online Resource Allocation, where the goal is to maximize value subject to resource budgets, and Online Load Balancing, where the goal is to minimize the makespan. We seek $(1\pmε)$-competitive algorithms in the large-budget or large-makespan regime. We consider a sampling model that generalizes the following two well-studied sampling models. In the Single-Sample Prophet Inequality ($\mathsf{SSPI}$) model, request $t$ is drawn from an unknown distribution $\mathcal{D}_t$, and the algorithm is given one independent sample from each $\mathcal{D}_t$ before the online phase. In the $p$-$\mathsf{Sample}$ model, the requests are adversarial, but a uniformly random $p$-fraction is revealed upfront as training data. Although near-optimal algorithms are known in the easier random-order model ($\mathsf{RO}$), where the requests arrive in a uniformly random order, prior algorithms for $\mathsf{SSPI}$ and $p$-$\mathsf{Sample}$ were problem-specific and incurred substantially worse dependencies on $ε$, $m$, and $n$. Our main contribution is a general framework that converts $\mathsf{RO}$ algorithms into algorithms for the $p$-$\mathsf{Preview}$ model, a model that generalizes both $\mathsf{SSPI}$ and $p$-$\mathsf{Sample}$. As consequences, we obtain near-optimal bounds for Online Resource Allocation, generalized Online Load Balancing, and online mixed packing-covering problems in these adversarial-order sampling models, significantly improving the bounds of [Ghuge, Singla, Wang (STOC'25)] and [Gupta and Molinaro (SODA'26)].

0.23

Minimization Prophet Inequality with Bounded Costs

cs.DS ·2026-09-06 ·Haolong Li, Xiaowei Wu
similarity 0.66
Abstract

We study the cost-minimization prophet inequality problem, in which a decision-maker sequentially observes $n$ independent and identically distributed (IID) random variables. After each observation, the decision-maker must either accept the current realization and stop, or reject it and continue with the next variable. The goal is to minimize the selected value. Unlike the classical maximization setting, if none of the first $n-1$ values is accepted, the final realization must be selected. Esfandiari et al. (SIDMA 2017) showed that this problem does not admit constant-competitive online algorithms in general, which motivates subsequent work on restricted distribution classes, such as entire distributions (Livanos and Mehta, SODA 2024) and distributions with bounded extreme values (Livanos and Mehta, EC 2025). In this work, we focus on distributions with bounded support. For distributions supported on $[1,b]$, we characterize the competitive ratio of online algorithms as a function of both $b$ and $n$. We consider both distribution-aware and distribution-oblivious settings. In the distribution-aware case, we provide a nearly tight characterization of the optimal online algorithm, showing that its competitive ratio is at most $b^{(1-1/n)^n}$ for all $n\geq 2$. More significantly, we design a distribution-oblivious algorithm that achieves the same guarantee, with a sequence of predetermined thresholds that depend only on $b$ and $n$. Furthermore, we extend our analysis to the non-IID setting, where we show that a simple single-threshold algorithm attains an asymptotically optimal competitive ratio of $Θ(\sqrt{b})$.

0.27

Metric Facility Location under Batched Random Order

cs.DS ·2026-11-03 ·Fabrizio Grandoni, Stefano Leonardi, Matteo Russo
theory similarity 0.66
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

Online Matching in Convex Bipartite Graphs

cs.DS ·2026-09-04 ·Yilong Feng, Zhihao Gavin Tang, Kangning Wang, Xiaowei Wu
similarity 0.65
Abstract · 29 pages

Online resource-allocation systems, like outpatient scheduling and spectrum allocation, often assign sequentially arriving requests to an ordered pool of scarce resources, where each request accepts a contiguous interval of feasible options. We study the resulting online matching problem on convex bipartite graphs under irrevocable decisions and adversarial arrivals. We first show that convexity alone does not improve the classic worst-case guarantee of 1-1/e, achieved by Ranking. We then consider the uniform-length model, in which every online request has exactly d consecutive offline neighbors. We propose Flip, which uses one random bit to commit ex-ante to either earliest-feasible assignment or latest-feasible assignment. Although either natural deterministic policy can waste capacity and be asymptotically only 1/2-competitive, we show that their randomized mixture is 2/3-competitive. This guarantee is tight for Flip and remains valid against a semi-adaptive adversary that observes the selected policy before choosing the arrival order. We also prove that no randomized online algorithm can achieve a competitive ratio strictly larger than 3/4 in the uniform-length model.

0.10