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

DOI10.1145/3284177zbMATH Open1427.91142arXiv1903.03944OpenAlexW2909539666MaRDI QIDQ4625673FDOQ4625673

Authors:

Publication date: 25 February 2019

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

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.

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

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

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)

Cited In (32)

• 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
• Title not available (Why is that?)
• Dynamic Relaxations for Online Bipartite Matching
• Secretary markets with local information
• Secretary markets with local information
• Primal beats dual on online packing LPs in the random-order model
• Attenuate locally, win globally: attenuation-based frameworks for online stochastic matching with timeouts
• Online allocation and display ads optimization with surplus supply
• Call admission problems on grids with advice
• 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
• Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds
• A dynamic near-optimal algorithm for online linear programming
• The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems
• Fast algorithms for online stochastic convex programming
• A stochastic algorithm for online bipartite resource allocation problems
• 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
• Title not available (Why is that?)

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)