Randomized online algorithms usually come with guarantees that hold only on average. The textbook ski-rental algorithm has an expected cost ratio of about 1.58 against the best offline choice, yet in a single run it has "more than a 37% chance of competitive ratio exceeding 2" (Controlling Tail Risk in Online Ski-Rental). A separate body of offline work on clustering takes a different route to hard problems. These are pseudo-approximations, which accept a small, controlled violation of a hard constraint, such as letting each facility serve $(1+\epsilon)$ times its capacity, in exchange for a guarantee that would otherwise be impossible (Constant Approximation for Capacitated k-Median with (1+epsilon)-Capacity Violation). This note asks whether that kind of slack can do something the online tail-risk literature has not considered: absorb the unlucky runs of a randomized algorithm.
The setting is online facility location with capacities. Clients arrive one at a time. The algorithm irrevocably opens facilities, each able to serve $u$ clients, and connects each client as it arrives. The standard randomized strategy, opening a facility at a client with probability proportional to that client's connection cost, is cheap on average. Its bad runs share a recognizable shape: too few facilities get opened near a dense region, nearby facilities fill up, and later clients pay long connections. Our claim is that a small capacity overflow, granted only at full facilities, cuts this tail risk far more than it cuts the average cost. Once overflow is allowed, the best tail-constrained opening rule also becomes simpler and smoother than the oscillating, discontinuous rules known for ski rental. If this holds, small slack is a cheap substitute for both heavy randomization and rigid determinism. If it fails, the slack is ordinary resource augmentation that lowers every measure of cost by the same factor, and we will be able to show that clearly.
Core Claim
Fix an instance and let $R$ be the realized ratio of the algorithm's cost to the offline optimum. The offline optimum always respects capacity $u$; the algorithm may load facilities up to $(1+\epsilon)u$. Tail risk is measured in two ways. The first is the tail constraint of Dinitz et al., $\Pr(R > \gamma) \le \delta$. The second is the conditional value-at-risk ratio of Christianson et al., which is the average of $R$ over the worst $(1-\delta)$ fraction of runs.
The hypothesis is that, for fixed $\epsilon$, the best achievable tail measure improves by a larger factor than the best achievable expected ratio. A second hypothesis concerns the "randomization cliff." This is the critical risk level $\delta^*$ beyond which randomness stops helping and a deterministic rule is optimal. Risk-Sensitive Online Algorithms put this level at $1-\Theta(1/\log B)$ for discrete ski rental with purchase cost $B$. We hypothesize that $\delta^*(\epsilon)$ moves measurably as $\epsilon$ grows. Either direction of movement would be informative. If the cliff moves toward smaller $\delta$, slack replaces randomness. If it moves toward larger $\delta$, slack makes randomness safe to use at higher risk aversion.
Why the Online Setting, Not Offline Rounding
The obvious way to join these directions is to measure the tail of the randomized rounding steps inside offline pseudo-approximation algorithms. Examples are the bi-point rounding of Li and Svensson and the dependent rounding of Demirci and Li. We reject this version. An offline solution's cost can be checked after the fact, so one can round many times and keep the best result, and the tail disappears at a polynomial cost in running time.
Tail risk matters only when decisions cannot be undone and only one run counts. That is the online regime. Existing work on online facility location with predictions, by Jiang et al. and Fotakis et al., uses this kind of randomized opening. It analyzes only expected cost, and it assumes facilities have unlimited capacity. Braun et al. handle capacities online with dependent rounding, again only in expectation and without slack. No paper in our search combines capacity slack with tail-constrained analysis. Yu and Shen do combine risk aversion with capacitated facility location, but only through scenario trees over a known distribution, with no worst-case guarantee.
Research Program
The first part is analytic and numerical, on a stripped-down model we call capacitated ski rental. In this model all clients arrive at a single point. Each client either "rents," paying a unit connection cost to a distant default, or is served by a purchased facility. A facility costs $B$ and serves $u$ clients, or $(1+\epsilon)u$ under slack. An adversary picks the total number of clients $n$.
Two features make the model useful. First, it contains discrete ski rental as the special case $u=\infty$, which ties it directly to the known cliff results. Second, it has the sawtooth worst cases that capacity creates: an adversary who stops just after a facility fills forces a nearly wasted second purchase.
For the tail-constrained version, the problem can be solved exactly as a linear program. The variables are a distribution over purchase schedules on a discretized client count. For each adversary choice $n$, the tail condition $\Pr(R>\gamma)\le\delta$ is linear in that distribution, and so is the expected ratio being minimized. We will solve this program over a grid of $(\epsilon,\delta,u,B)$. From the solutions we will record three things: the expected-ratio-versus-tail frontier, the cliff location $\delta^*(\epsilon)$, and the number of zero-probability gaps in the optimal purchase distribution. For the conditional value-at-risk measure, we will use the parameterization through the inverse cumulative distribution introduced by Christianson et al. and solve numerically. We will then try to prove the shape of $\delta^*(\epsilon)$ that the numbers suggest.
The second part turns these schedules into an online capacitated facility location algorithm. Its base is the prediction-guided randomized opening of Jiang et al.. On top of it we add an overflow rule: a client whose nearest open facility is full may still be assigned there, up to $(1+\epsilon)u$. We also replace the default opening probability with a tail-tuned rule inside each dense region, taken from the first part's solutions. The intended guarantee is three-part: a bound on realized overflow that holds in every run, a tail bound on $R$, and an expected ratio close to that of the untuned algorithm.
Baselines
The naive reference point is randomized opening with strict capacities, with no overflow and no tuning. When the nearest facility is full, the client goes to the nearest facility with room, or opens a facility under the usual random rule. This shows how much tail capacity creates in the first place.
The strongest existing method is the prediction-based algorithm of Fotakis et al., which is 2-consistent and robust in the uncapacitated case. It will be run with the same strict capacity rule and the same predictor. That predictor follows Jiang et al. and is trained on 30% of the data, the regime where Jiang et al. report "outperforming the baseline by nearly a factor of two in some cases" on the Non-Uni dataset. That is the only reported figure available. No reported result was found on Lacuna for any capacitated online facility location algorithm on these datasets, and none for tail or risk metrics of any online facility location algorithm.
Three further baselines isolate the key ingredient. The first is uniform augmentation: the untuned randomized algorithm run with capacity $(1+\epsilon)u$ everywhere. This tests whether gains come from tuning the randomness to the slack or merely from extra capacity. The second is a deterministic opening rule given the same slack. It opens once the accumulated connection cost in a region exceeds the opening cost. The third is the coin-flip mixture of the randomized and deterministic algorithms, which Dinitz et al. prove suboptimal for ski rental.
All methods share the same instances, arrival orders, predictor, and random seeds. Every method that has a free parameter gets the same tuning budget, a grid of 20 settings chosen on a held-out set of arrival orders. Our method beats a baseline if two conditions both hold on at least three of four datasets. First, at equal or lower expected ratio, its worst-1%-average ratio is at least 25% lower. Second, its realized overflow never exceeds $\epsilon u$.
Why not just…?
Why not just run several independent copies and keep the best? Online, facilities are opened irrevocably, so only one run ever exists. This is exactly why we leave out the offline rounding version, where repetition does work.
Why not just mix the randomized and deterministic algorithms with a biased coin? Controlling Tail Risk in Online Ski-Rental proves this mixture strictly suboptimal for ski rental. Whether that remains true under slack is open. The mixture is therefore run as a baseline in both the exact linear programs and the facility experiments.
Why not just give every facility $(1+\epsilon)u$ capacity and keep the standard algorithm? This is the real threat, since it is ordinary resource augmentation. The uniform-augmentation baseline settles it. If uniform augmentation matches our tuned algorithm on tail measures, and the exact programs show that slack shifts expected and tail frontiers by the same factor, then the core claim is false, and we will report it that way.
Why not just use a deterministic algorithm, since slack already prevents blow-ups? A deterministic rule with slack is a baseline. If it wins at every $\delta$, that means the cliff has moved to zero, which is a clean answer to the question.
Why not just use scenario-tree stochastic programming? Yu and Shen require a known demand distribution. We therefore also evaluate adversarial arrival orders, where that assumption fails.
Proposed Experiments
The datasets are Twitter, Adult, US-PG, and Non-Uni from Jiang et al.. Each will be subsampled to roughly 2,000 points so that the offline capacitated optimum can be computed by an integer program. Where the solver times out, we will fall back to the linear relaxation, which is a valid lower bound and so makes the reported ratios pessimistic. Capacities will be set to $u \in \{n/50, n/20\}$, and slack to $\epsilon \in \{0, 0.05, 0.1, 0.25\}$. Arrival orders will be random, and also adversarial, with points sorted by cluster so that density arrives in bursts.
Each configuration gets 1,000 seeds. For each we report the expected ratio, $\Pr(R>\gamma)$ with $\gamma$ set to twice the strict baseline's expected ratio, the average ratio over the worst 10% and worst 1% of runs, and the realized maximum overflow.
There are two decisive checks. The first comes from the exact capacitated ski-rental programs. For our claim to survive, the ratio of tail improvement to expected improvement must exceed 1 for some $\epsilon$, and $\delta^*(\epsilon)$ must move measurably. If both stay flat, the claim is refuted before the facility experiments are run. The second check is the facility experiments at matched expected cost, where the tuned overflow algorithm must beat uniform augmentation on the worst-1% ratio. Passing only the first check would show the effect exists in theory but is lost in realistic metrics. Passing both would make capacity slack a practical tool for bounding tail risk.
References
- Controlling Tail Risk in Online Ski-Rental
- Constant Approximation for Capacitated k-Median with (1+epsilon)-Capacity Violation
- Risk-Sensitive Online Algorithms (Extended Abstract)
- Approximating k-median via pseudo-approximation
- Online Facility Location with Predictions
- Improved Bounds for Online Facility Location with Predictions
- Approximating Optimum Online for Capacitated Resource Allocation
- On the Value of Multistage Risk-Averse Stochastic Facility Location With or Without Prioritization