CS Paper Radar

Online Allocation using Few Samples

Matthew Faw, Sahil Singla, Yifan Wang

cs.DS cs.GT ·submitted 2026-09-15 15:44 UTC · v1

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

Closest papers

Nearest neighbours by meaning across the whole index.

Beyond Worst-Case Online Algorithms via Input Subsampling

cs.DS cs.GT ·2026-11-11 ·Siddhartha Banerjee, Tianle Jiang, Kamesh Munagala
published similarity 0.75
Abstract · Accepted to ITCS 2027

We study whether classical competitive ratios survive input subsampling, when both the online algorithm and the offline optimum are evaluated on the same subsampled input. We consider the canonical problems of prophet inequalities and ski-rental. In these settings, for any single subsampling rate, the classical worst-case ratios remain unchanged. We ask a stronger question: can one adversarial input remain worst-case at two distinct rates $p>q$? For prophet inequalities, in the model where the policy knows the sampling rate and learns item survival online, every instance has competitive ratio strictly below $2$ at one of the two rates, and we determine the tight simultaneous guarantee. For ski rental, in the fluid model where sampling scales the horizon, the answer depends on $q/p$. Against adversarial distributions over horizons, one unrestricted randomized algorithm achieves a strict simultaneous improvement over $e/(e-1)$ for every distribution exactly when $q/p$ is below approximately $0.34$. Requiring the algorithm to buy by the breakeven time lowers this threshold to approximately $0.31$, showing that unlike classical ski-rental algorithms, buying later can provably help in this setting. Our results therefore reveal a new form of beyond-worst-case fragility under input subsampling: instances that are worst-case at one rate need not remain hard at two rates simultaneously.

0.20

Single-or-Sample: Online Fair Allocation for Combinatorial Agents

cs.GT cs.DS ·2026-09-26 ·Shuchi Chawla, Zhiyi Huang, Pooja Kulkarni, Ruta Mehta, Parnian Shahkar
similarity 0.72
Abstract · 48 pages

We study the fair allocation of $m$ indivisible goods among $n$ heterogeneous agents arriving online, under maximin share (MMS) fairness. The key challenge lies in making allocation decisions in an adversarial setting without knowing future agents' valuations. No guarantees were known prior to our work in adversarial settings. Our main positive result is an online allocation algorithm for submodular agents that with probability at least $0.4$ guarantees a $1/24$-approximation to MMS to all agents simultaneously. Our algorithm intersperses a greedy-style adaptive sampling-without-replacement protocol with single-good reduction rounds. For XOS valuations, we adapt this single-or-sample approach to guarantee a $c$-MMS for all agents simultaneously with probability $1-O(c)$ for any parameter $c\in O(1/\log n)$. A key technical contribution of our work is in establishing Chernoff-style tail bounds on item allocation events for this adaptive sampling process despite strong positive correlations among the items, a result that may be of independent interest. The approximation versus success probability tradeoffs achieved by our algorithms are asymptotically tight. We show that even for binary additive valuations, no randomized algorithm can ensure $c$-MMS to all agents with probability exceeding $(1-c^2/5)$, for any $c\in (0,1]$. For XOS valuations, stronger lower bounds hold: no randomized algorithm can ensure $c$-MMS to all agents with probability exceeding $(1-c/3)$, for any $c\in (0,1]$. Furthermore, no algorithm can achieve $ω(1/\log \log n)$-MMS with any constant probability. All our lower bounds hold even for simple binary instances whose MMS values and MMS partitions can be computed in linear time.

0.31

Optimal Contention Resolution from Samples

cs.DS cs.GT ·2026-11-05 ·Shaddin Dughmi, Vasilis Livanos, Pranav Nuti
theory similarity 0.69
Abstract

Contention resolution schemes convert random sets which are ex-ante feasible for some constraint into sets which are feasible ex post, and their online variants have broad applications in Bayesian and stochastic optimization, including prophet inequalities and stochastic probing. In many such applications, however, full distributional knowledge is an unattainable requirement. This motivates the study of contention resolution schemes which employ a limited number of samples from the underlying distributions. We study sample-based contention resolution for $k$-uniform matroids, for both uniformly random and adversarial arrival orders, and compare their balance guarantees to the best possible with full distributional knowledge. For a single-item constraint, we show that one sample per element suffices for an optimal $(1-1/e)$-balanced ROCRS. For adversarial arrivals, however, we prove that no single-sample OCRS can be $1/2$-balanced, even for known arrival orders, separating contention resolution from prophet inequalities in the single-sample setting. Perhaps surprisingly, we show that two samples are necessary and sufficient for the optimal $1/2$ guarantee. We also present a single-sample $0.48$-balanced scheme. For general $k$, we give a simple single-sample ROCRS that achieves an optimal balance ratio of $1-e^{-k}k^k/k!$. In adversarial order, we obtain a single-sample $(1 - O(1/\sqrt{k}))$-balanced scheme, matching the optimal asymptotic dependence on $k$. Finally, we complete the picture by characterizing the minimum number of samples needed to match the optimal balance ratio achievable with full distributional knowledge. For random arrivals, one sample suffices for $k = 1,2,3,4$, and zero samples suffice for $k \geq 5$. For an adversarial arrival order, even known in advance, and any $k \geq 2$, we show that no constant number of samples suffices to achieve optimal balance.

0.20

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

Balanced Sampling in Stochastic Multi-objective Bandits

cs.LG stat.ML ·2026-10-26 ·Mengfan Xu
theory similarity 0.69
Abstract

In stochastic multi-objective bandits, Pareto optimal arms may represent different trade-offs among objectives. Balanced sampling across them is important in practical settings such as online advertising. Yet, there seems to be little consensus on how to measure fairness, to our best knowledge. Achieving fairness is also tough as the set of Pareto optimal arms is unknown, and early sampling decisions may create imbalances that are difficult to erase afterwards. We measure unfairness by the KL divergence from the uniform distribution over the true Pareto set to the empirical measure induced by the sampling trajectory. Nicely, this measure admits an exact decomposition that separates the cost of sampling suboptimal arms from the imbalance among Pareto optimal arms. With a recursive form for unfairness, we develop \emph{adaptive top-two sampling}, which combines sampling counts and empirical evidence of Pareto membership to define a gain for each arm and guide sampling without committing to an estimated Pareto set. When the Pareto set is stable under small perturbations, we establish an $O(\log T/T)$ and $O(T^{-1})$ bound on expected unfairness and variance, respectively. Information-theoretic lower bounds show that the $\log T/T$ rate can be unavoidable for uniformly fair policies on stable instances, matching our upper bound. More surprisingly, stability is indeed crucial, as the expected unfairness can be $ω(\log T/T)$ without it. Finally, we create a variant that encourages exploration of undersampled arms to reduce the risk of persistent underallocation. At sufficiently large horizons, it preserves the rate on the expected unfairness while admitting a sharper bound of $O(\log^2 T/T^2)$ on variance. Numerical studies support these findings and suggest practical insights.

0.21

Online Matching in Convex Bipartite Graphs

cs.DS ·2026-09-04 ·Yilong Feng, Zhihao Gavin Tang, Kangning Wang, Xiaowei Wu
similarity 0.69
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

Tight Bounds for Downward-Closed Prophet and Secretary Problems

cs.GT cs.DS ·2026-11-12 ·Hanrui Zhang
similarity 0.69
Abstract

We study online selection problems subject to arbitrary downward-closed feasibility constraints, under different arrival orders, with different distributional assumptions. We establish the following bounds: (1) $Θ(\log^2 n / \log \log n)$ for the standard (adversarial-order) prophet problem, (2) $Ω(\log n)$ for the (Bayesian, random-order) prophet secretary problem, and by extension, for the standard (prior-free, random-order) secretary problem, and (3) $O(\log n / \log \log n)$ for the free-order prophet problem. Together with complementary bounds established in prior work, these results pin down the asymptotically tight competitive ratios for all these variants of prophet and secretary problems subject to downward-closed constraints. Our results refine and reinforce the big-decisions-first principle by Rubinstein and Singla [2026], establishing a superconstant separation between the random-order and free-order models.

0.14

Degree-Parameterized Analysis of Sampling-Based Online Matching

cs.DS cs.GT ·2026-09-13 ·Pan Xu
publishedtheory similarity 0.68
Abstract · A preliminary version of this work has been accepted to WINE 2026

We study edge-weighted online bipartite matching under random arrival order, parameterized by the maximum offline degree $d$ and sampling fraction $θ$. We analyze two sampling-based frameworks. For \emph{Deterministic Greedy Sampling}, which computes prices from a fixed-size initial sample and then applies a local threshold rule, we derive an explicit worst-case competitive ratio and prove it tight within this policy family for every fixed $d\ge2$ and $θ\in[0,1]$. The optimal sampling choice interpolates between no sampling for $d=1,2$ and a dense-limit guarantee of approximately $0.2562$, improving on the classical $1/8$ analysis while retaining linear per-arrival time. We also derive worst-case bounds on the variance of the number of matched offline agents, including order-tight behavior as $θ\to1_-$ and an $O(θ)$ bound as $θ\to0_+$ for fixed $m,d$. For \emph{Black-Box Sampling--Matching}, we introduce prefix-dependent reweighting followed by an arbitrary approximate offline matching solver and prove a transfer theorem whose guarantee is the offline approximation ratio times an explicit function of $d$ and $θ$. With exact matching, the framework recovers the classical $1/e$ guarantee in the unbounded-degree limit.

0.28