Online allocation improves with few samples from adversarial inputs
Online Allocation using Few Samples
Data Structures and AlgorithmsComputer Science and Game Theory
Summary
This paper studies how to handle requests that arrive one by one in a worst-case order, where decisions must be made immediately without the chance to change them later. The authors focus on ways to use just a few preview samples of the requests to make nearly optimal choices, even when the total resources or task sizes are large. Their main contribution is a general method that transforms algorithms designed for randomly ordered requests into ones that work well with limited preview samples, which covers previously studied models as special cases. This approach leads to better performance guarantees for problems involving resource allocation and load balancing under tough input conditions.
What this means in practice
- •For cloud resource managers: Improve task scheduling by using limited prior data to better allocate resources as requests arrive unpredictably.
- •For manufacturing line supervisors: Optimize job distribution across machines using small samples of incoming tasks to prevent workload overload efficiently.
Authors
Matthew Faw, Sahil Singla, Yifan Wang
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)].