Near optimal online algorithms and fast approximation algorithms for resource allocation problems

DOI10.1145/3284177MaRDI QIDQ4625673zbMATH OpenOpenAlexFDO

Authors

Publication date 25 February 2019

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1903.03944

zbMATH Keywords

online algorithmsgreedy algorithmapproximation algorithmsunknown distribution

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Combinatorial optimization (90C27) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Approximation algorithms (68W25)

Abstract: We present prior robust algorithms for a large class of resource allocation problems where requests arrive one-by-one (online), drawn independently from an unknown distribution at every step. We design a single algorithm that, for every possible underlying distribution, obtains a $1-epsilon$ fraction of the profit obtained by an algorithm that knows the entire request sequence ahead of time. The factor $epsilon$ approaches $0$ when no single request consumes/contributes a significant fraction of the global consumption/contribution by all requests together. We show that the tradeoff we obtain here that determines how fast $epsilon$ approaches $0$, is near optimal: we give a nearly matching lower bound showing that the tradeoff cannot be improved much beyond what we obtain. Going beyond the model of a static underlying distribution, we introduce the adversarial stochastic input model, where an adversary, possibly in an adaptive manner, controls the distributions from which the requests are drawn at each step. Placing no restriction on the adversary, we design an algorithm that obtains a $1-epsilon$ fraction of the optimal profit obtainable w.r.t. the worst distribution in the adversarial sequence. In the offline setting we give a fast algorithm to solve very large LPs with both packing and covering constraints. We give algorithms to approximately solve (within a factor of $1+epsilon$) the mixed packing-covering problem with $O(fracgammamlog(n/delta)epsilo{n}^2)$ oracle calls where the constraint matrix of this LP has dimension $nimesm$, the success probability of the algorithm is $1-delta$, and $gamma$ quantifies how significant a single request is when compared to the sum total of all requests. We discuss implications of our results to several special cases including online combinatorial auctions, network routing and the adwords problem.

Recommendations

• Primal beats dual on online packing LPs in the random-order model
• Online stochastic packing applied to display ad allocation
• A dynamic near-optimal algorithm for online linear programming
• Primal beats dual on online packing LPs in the random-order model
• A stochastic algorithm for online bipartite resource allocation problems

Cited in

(32)

• scientific article; zbMATH DE number 7053386 (Why is no real title available?)
• Algorithms – ESA 2004
• On-line resource management with applications to routing and scheduling
• Bicriteria online matching: maximizing weight and cardinality
• Per-round knapsack-constrained linear submodular bandits
• scientific article; zbMATH DE number 1839473 (Why is no real title available?)
• Secretary markets with local information
• Dynamic Relaxations for Online Bipartite Matching
• Secretary markets with local information
• Attenuate locally, win globally: attenuation-based frameworks for online stochastic matching with timeouts
• Primal beats dual on online packing LPs in the random-order model
• Call admission problems on grids with advice
• Online allocation and display ads optimization with surplus supply
• Online assortment and market segmentation under Bertrand competition with set-dependent revenues
• Online Submodular Maximization Problem with Vector Packing Constraint.
• Asymptotic analysis for multi-objective sequential stochastic assignment problems
• Online resource allocation under partially predictable demand
• Online stochastic matching: new algorithms and bounds
• Competitive online algorithms for resource allocation over the positive semidefinite cone
• Online max-min fair allocation
• Online stochastic packing applied to display ad allocation
• A dynamic near-optimal algorithm for online linear programming
• Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds
• A stochastic algorithm for online bipartite resource allocation problems
• The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems
• Fast algorithms for online stochastic convex programming
• Autobidding with constraints
• Optimal dynamic multi-keyword bidding policy of an advertiser in search-based advertising
• The online best reply algorithm for resource allocation problems
• Randomized approximation and online algorithms for assignment problems
• Know when to persist: deriving value from a stream buffer
• Adversarial bandits with knapsacks

This page was built for publication: Near optimal online algorithms and fast approximation algorithms for resource allocation problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4625673)