CS Paper Radar

The Competitive Ratio of Online Budgeted Allocation is Strictly Smaller than $1-1/e$

Debmalya Panigrahi, Ian Zhang

cs.DS cs.GT ·submitted 2026-10-30 01:47 UTC · v1

Abstract

A well-known conjecture in online algorithms is that the (randomized) competitive ratio of online budgeted allocation is $1-1/e$. We refute this conjecture and show that every randomized online algorithm has competitive ratio at most $1 - 1/e - \varepsilon$ for a (small) absolute constant $\varepsilon > 0$.

Closest papers

Nearest neighbours by meaning across the whole index.

Randomized Algorithm for MMS Allocation of Chores with Online Agent Arrivals

cs.GT ·2026-10-11 ·Haolong Li, Fangxiao Wang, Xiaowei Wu
similarity 0.68
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

Efficient Algorithms for Online Subadditive Combinatorial Allocations

cs.DS cs.GT ·2026-10-06 ·Calum MacRury, Rian Neogi, Kanstantsin Pashkovich, Sahil Singla, Siddharth M Sundaram +1 more
similarity 0.68
Abstract

For the online combinatorial allocation problem with subadditive valuations, Correa and Cristi (STOC 2023) proved the existence of a $6$-competitive online algorithm, improving on the previous best $O(\log\!\log m)$-competitive online algorithm due to Dütting, Kesselheim, and Lucier (FOCS 2020), where $m$ is the number of items. However, Correa and Cristi's result is existential, and it was left open whether a constant competitive ratio is attainable via an efficient online algorithm that uses a polynomial number of demand oracle queries. In this work, we answer this affirmatively, giving an expected-polynomial-time $(6 + ε)$-competitive online algorithm for any constant $ε> 0$. Our techniques also recover, in the offline setting, the $(2 + ε)$-approximation result of Feige (STOC, 2006). Finally, when the buyers' valuations are drawn from identical distributions, we exploit symmetry to obtain an improved $(60/11+ε)$-competitive algorithm. Starting with the natural configuration LP relaxation for the problem, our main technical contribution is a recursive Bundle Score Generator (BSG) that resolves item conflicts by assigning correlated scores to the items requested by each buyer. Unlike the Random Score Generator whose existence is shown by Correa and Cristi, our BSG is efficiently computable in expected polynomial time. Moreover, it satisfies a stochastic dominance property that is sufficient to recover both Feige's offline result and Correa and Cristi's online result.

0.28

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.67
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 under an Oblivious Adversary

cs.GT ·2026-09-23 ·Saar Cohen, Nicholas Teh, Michael Wooldridge
benchmark similarity 0.67
Abstract

We study online fair division, where indivisible goods arrive one at a time and must be allocated immediately and irrevocably among $n\ge2$ agents. Against an oblivious adversary that fixes the input in advance, we ask what fairness guarantees randomized online algorithms can achieve. We present the Deficit Allocation (DA) algorithm, which improves the previously known high-probability approximation to PROP1 from inverse-logarithmic to inverse-doubly-logarithmic in $n/δ$, where $δ$ is the failure probability. DA does not require $δ$ as input. With probability at least $1-δ$, a refined variant achieves an arbitrarily close approximation to proportionality when no single item is too valuable relative to an agent's proportional share; without any restriction on item values, it obtains an arbitrarily close approximation to PROP$k$ for $k$ doubly logarithmic in $n/δ$. For $n2^{-2n}\leδ\le1/2$, our bounds on the approximation factor and $k$ are asymptotically tight for the stronger fractional benchmark that divides each item equally among the agents who value it positively. We also prove that algorithms that use only which agents value each item positively, but not by how much, cannot improve upon the logarithmic dependence of uniformly random allocation. However, other fairness notions admit weaker guarantees. For EF1, every randomized online algorithm has an input on which any positive approximation succeeds with probability at most $e^{-Ω(n)}$. For EFX, this probability is at most $1/n!$ with only $n+1$ items, tight within a factor of $(n+1)/2$; for MMS, it can be at most $5/6$. Finally, allocating each item uniformly among the agents who value it positively gives, with probability at least $1-δ$, an arbitrarily close approximation to EF$k$ for $k$ logarithmic in $n/δ$, and this dependence is necessary for this rule.

0.28

A Tight $\widetilde Ω(\sqrt{m})$ Information-Theoretic Lower Bound for Randomized Online Set Cover

cs.DS ·2026-09-10 ·Ilan Doron-Arad, Joseph, Naor
theory similarity 0.66
Abstract

Online set cover is a fundamental problem in online algorithms, admitting a deterministic $O(\log m\log n)$-competitive algorithm, where $m$ is the number of sets and $n$ is the number of elements. This is essentially tight for deterministic algorithms as well as for polynomial-time randomized algorithms assuming $\mathrm{NP}\not\subseteq\mathrm{BPP}$. However, the best lower bound known for information-theoretic (computationally unlimited) randomized algorithms against an oblivious adversary is only $Ω(\log m)$, whereas the upper bound in terms of $m$ is $O(\sqrt m\log m)=\widetilde O(\sqrt m)$. We prove an $Ω(\sqrt m)$ lower bound for information-theoretic randomized unweighted online set cover, showing that even with unbounded computational power, randomization cannot achieve an $O(\log m)$-competitive ratio. Specifically, our lower bound rules out $O(\log m\cdot\log^{1/2-\varepsilon} n)$-competitive algorithms for every constant $\varepsilon>0$. Our techniques also prove an $Ω(m^{1/3})$ lower bound in the random-order model, and show that every algorithm with $poly(m)$ memory has competitive ratio $Ω(m/\log m)$, even with unlimited computation between requests.

0.25

Online Fair Division: Pushing the Frontier of Approximate Proportionality

cs.GT ·2026-09-12 ·Yingjian Du, Ankang Sun
theoryhighly cited similarity 0.66
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

Randomized Online Fair Division: High-Probability and Expected Realized Fairness

cs.GT ·2026-09-20 ·Tianqi Chen, Jingxiao Long
similarity 0.66
Abstract · 22 pages. Improved high-probability and expected realized PROP1 guarantees; revised proofs and exposition

We study randomized algorithms for the fully online allocation of indivisible goods among $n\ge2$ agents with nonnegative additive valuations. Goods arrive sequentially and must be allocated immediately and irrevocably, with only $n$ known in advance. Since exact ex-ante envy freeness and proportionality are readily achievable, while no positive ex-post approximation is possible for the fairness notions considered here, we study the intermediate notions of high-probability fairness and expected realized fairness. Against a non-adaptive adversary, we give a randomized algorithm for proportionality up to one good (PROP1) whose parameter depends only on $n$ and that preserves exact ex-ante envy-freeness and proportionality. At confidence $1-δ$, its PROP1 guarantee improves on independent uniform allocation (Rand) by a factor of $Ω(\log n)$, uniformly over $δ\in(0,1/2]$. As $n\to\infty$, its expected realized PROP1 factor is at least $\frac{3-\sqrt5}{2}-o(1)$. We also show that the expected realized PROP1 factor of Rand is $(1+o(1))/\log n$, yielding an improvement of at least $\bigl(\frac{3-\sqrt5}{2}-o(1)\bigr)\log n$ for our algorithm. For every randomized online algorithm and every positive approximation factor, the success probability can be made arbitrarily small for envy freeness up to any good (EFX) and at most $\frac{n+1}{2n}$ for envy freeness up to one good (EF1). Consequently, every randomized fully online algorithm has an expected realized EFX guarantee of zero and an expected realized EF1 guarantee of at most $\frac{n+1}{2n}$.

0.43

Online Graph Coloring: Competitive Ratios Separating Randomized and Deterministic Algorithms

cs.DS cs.DMmath.CO ·2026-11-10 ·Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda
theory similarity 0.65
Abstract

We study online coloring, focusing on the competitive ratio. The best previously known results were (1) a lower bound of $Ω(n / \log^2 n)$ for both deterministic and randomized algorithms by Halldórsson and Szegedy (1994), (2) an upper bound of $O(n / \log n)$ for randomized algorithms by Halldórsson (1997), and (3) an upper bound of $O(n / \log \log n)$ for deterministic algorithms by Kawarabayashi, Yoneda, and Yoneda (2025). In this paper, we improve these results as follows: 1. A new lower bound of $Ω(n / \log n)$ for deterministic algorithms. 2. A new upper bound of $O(n (\log \log n)^2 / \log^2 n)$ for randomized algorithms. 3. A new upper bound of $O(n / (\log \log n)^{2-\varepsilon})$ for deterministic algorithms for every fixed $\varepsilon>0$. For randomized algorithms, we nearly close the gap between the lower and upper bounds; the remaining gap is only $O((\log \log n)^2)$. We establish the asymptotic separation between randomized and deterministic online graph coloring. Against an oblivious adversary, a polynomial-time randomized algorithm achieves a competitive ratio asymptotically smaller than any deterministic algorithm can guarantee, even with unlimited computation.

0.17