Source-linked AI summary
Primal Beats Dual on Online Packing LPs in the Random-Order Model
Thomas Kesselheim, Klaus Radke, Andreas Tönnis, Berthold Vöcking
TL;DR
The paper studies online packing LPs with randomly ordered requests, where existing algorithms require sufficiently large capacity ratios. It presents an adaptive algorithm requiring little prior information and achieves a (1 − ε)-competitive guarantee when B=Ω((log d)/ε^2), while matching known lower bounds in key cases.
Problem
Online packing LPs are studied when requests arrive in uniformly random order, a setting where prior primal-dual algorithms require sufficiently large capacity ratios.
Method
The algorithm avoids a sampling phase and adapts without requiring prior knowledge of B or d.
Results
B=Ω((log d)/ε^2) suffices for a (1 − ε)-competitive algorithm, and the result matches known lower bounds for d=m and d=1.
Takeaways & Limitations
The approach closes the exponential capacity-ratio gap in terms of m and gives the first capacity-ratio results in terms of d.
Takeaways & Limitations
For small capacities, no ε<1 yields a (1 − ε)-competitive guarantee; the analysis instead provides a non-trivial bound for B≥2.
Abstract
from arXiv · showhide
We study packing LPs in an online model where the columns are presented to the algorithm in random order. This natural problem was investigated in various recent studies motivated, e.g., by online ad allocations and yield management where rows correspond to resources and columns to requests specifying demands for resources. Our main contribution is a $1-O(\sqrt{(\log{d})/B})$-competitive online algorithm, where $d$ denotes the column sparsity, i.e., the maximum number of resources that occur in a single column, and $B$ denotes the capacity ratio $B$, i.e., the ratio between the capacity of a resource and the maximum demand for this resource. In other words, we achieve a $(1 - ε)$-approximation if the capacity ratio satisfies $B=Ω((\log d)/ε^2)$, which is known to be best-possible for any (randomized) online algorithms. Our result improves exponentially on previous work with respect to the capacity ratio. In contrast to existing results on packing LP problems, our algorithm does not use dual prices to guide the allocation of resources. Instead, it simply solves, for each request, a scaled version of the partially known primal program and randomly rounds the obtained fractional solution to obtain an integral allocation for this request. We show that this simple algorithmic technique is not restricted to packing LPs with large capacity ratio: We prove an upper bound on the competitive ratio of $Ω(d^{-1/(B-1)})$, for any $B \ge 2$. In addition, we show that our approach can be combined with VCG payments and obtain an incentive compatible $(1-ε)$-competitive mechanism for packing LPs with $B=Ω((\log m)/ε^2)$, where $m$ is the number of constraints. Finally, we apply our technique to the generalized assignment problem for which we obtain the first online algorithm with competitive ratio $O(1)$.
1 Introduction
The paper studies online packing LPs with randomly ordered requests and presents a primal-based algorithm whose guarantees depend on column sparsity and capacity ratio. It closes prior capacity-ratio gaps, works without advance knowledge of key instance parameters, and extends to truthful mechanisms and generalized assignment.
- Problem setting: Online packing LPs reveal columns over time, requiring irrevocable resource allocations under capacity constraints while maximizing profit.The random-order model randomizes the request permutation, while capacities and the number of requests are known initially.
- Main result: 1 − O(sqrt((log d)/B))-competitive performance is achieved when the capacity ratio satisfies B = Ω((log d)/ε^2), where d is column sparsity.This closes the exponential capacity-ratio gap and matches the known lower bound in the general case d = m.
- Algorithm: The method needs no sampling phase and adapts without prior knowledge of B, d, demands, or objective coefficients.Existing primal-dual methods generally require capacity-ratio information and may reserve an initial sampling phase without allocations.
- Algorithm: The algorithm solves a scaled revealed primal LP for each request and randomly rounds the current fractional allocation into an integral tentative option.When ℓ requests are visible, capacities are scaled to ℓ/n times the original vector; an option is allocated permanently only if it preserves feasibility.
2 A Robust Algorithm for Online Packing LPs
The algorithm repeatedly solves a capacity-scaled LP over revealed requests, randomly rounds the current request’s fractional allocation, and keeps it only when feasible. Its analysis combines expected objective bounds with concentration arguments to obtain strong guarantees for large capacities and nontrivial guarantees for small capacities.
- Algorithm: At round ℓ, solve the optimal fractional LP for revealed requests with capacities scaled by ℓ/n, then use the current request’s fractional allocation as a probability distribution over options.The selected tentative option is accepted only if it preserves feasibility under the original capacities; otherwise the request is discarded.
- Algorithm: The algorithm is invariant under constraint scaling, so demands can be normalized to at most one and the minimum capacity becomes the relevant capacity parameter.Under this normalization, B equals bmin, the minimum resource capacity.
- Analysis: The proof bounds the expected value of each scaled LP, the probability that constraints are exhausted, and the total expected value accumulated across rounds.The locally optimal solution is order-independent conditional on the revealed set, allowing the current request to be treated as uniformly drawn from known requests.
- Analysis: Correlated tentative allocations are handled with 1-correlated random variables and Chernoff bounds, including when allocations across rounds are not independent.The analysis uses unbiasedness of earlier randomization under suitable conditioning to control constraint consumption.
- High Capacities: 1 − O(√((log d)/bmin))-approximation is achieved for column sparsity at most d when capacities satisfy the paper’s large-capacity condition.The theorem states that the guarantee holds even relative to the optimal fractional solution.
3 Extensions and Variants
The extensions adapt the primal-and-rounding approach to truthful packing mechanisms and online generalized assignment, including sampling for known capacity parameters and a constant-competitive GAP algorithm.
- Truthful online packing: Algorithm 2 removes infeasible options before applying Algorithm 1 and VCG payments, yielding truthfulness in expectation even when bidders know the random order.The mechanism preserves truthful reporting under the stated random-order setting.
- Truthful online packing: Theorem 6 gives truthful reports a social-welfare approximation factor of 1-O.The supplied theorem statement truncates the bound after 1-O.
- Sampling variant: For small B, Algorithm 1 can exhaust resources early because its allocation is optimistic, whereas knowing B and d enables an initial sampling phase.The sampling phase makes no allocation during the first pn rounds.
- Online generalized assignment: GAP contains edge-weighted matching, knapsack, unweighted bipartite matching, and AdWords as special cases, while the construction represents each bin choice as a packing-LP column.The formulation uses option sizes as resource coefficients and profits as objective coefficients.
- Online generalized assignment: The GAP algorithm separates options into heavy and light cases, then randomly chooses between edge-weighted matching and the online primal-rounding procedure.Heavy options consume more than half a bin's capacity; light options consume at most half.
- Online generalized assignment: For light options, each arriving item uses the current visible-item LP relaxation, interprets its fractional allocation as probabilities, and rounds it online.The analysis bounds prior expected bin consumption and combines tentative-profit and success-probability bounds.