Online contention resolution schemes
From MaRDI portal
Publication:4575652
Abstract: We introduce a new rounding technique designed for online optimization problems, which is related to contention resolution schemes, a technique initially introduced in the context of submodular function maximization. Our rounding technique, which we call online contention resolution schemes (OCRSs), is applicable to many online selection problems, including Bayesian online selection, oblivious posted pricing mechanisms, and stochastic probing models. It allows for handling a wide set of constraints, and shares many strong properties of offline contention resolution schemes. In particular, OCRSs for different constraint families can be combined to obtain an OCRS for their intersection. Moreover, we can approximately maximize submodular functions in the online settings we consider. We, thus, get a broadly applicable framework for several online selection problems, which improves on previous approaches in terms of the types of constraints that can be handled, the objective functions that can be dealt with, and the assumptions on the strength of the adversary. Furthermore, we resolve two open problems from the literature; namely, we present the first constant-factor constrained oblivious posted price mechanism for matroid constraints, and the first constant-factor algorithm for weighted stochastic probing with deadlines.
Recommendations
- Online contention resolution schemes with applications to Bayesian selection problems
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint
- Submodular secretary problem and extensions
Cited in
(23)- Submodular maximization with uncertain knapsack capacity
- scientific article; zbMATH DE number 7765403 (Why is no real title available?)
- Buy-many mechanisms for many unit-demand buyers
- Prophet inequalities for independent and identically distributed random variables from an unknown distribution
- Optimal item pricing in online combinatorial auctions
- Prophet secretary for \(k\)-knapsack and \(l\)-matroid intersection via continuous exchange property
- An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint
- Prophet inequalities made easy: stochastic optimization by pricing nonstochastic inputs
- Contention resolution, matrix scaling and fair allocation
- Posted price mechanisms and optimal threshold strategies for random arrivals
- Towards an optimal contention resolution scheme for matchings
- Guess free maximization of submodular and linear sums
- Formal barriers to simple algorithms for the matroid secretary problem
- Optimal item pricing in online combinatorial auctions
- Online contention resolution schemes with applications to Bayesian selection problems
- Prophet inequalities vs. approximating optimum online
- Prophet matching with general arrivals
- Improved prophet inequalities for combinatorial welfare maximization with (approximately) subadditive agents
- A simple optimal contention resolution scheme for uniform matroids
- scientific article; zbMATH DE number 7378727 (Why is no real title available?)
- Optimal prophet inequality with less than one sample
- Approximation algorithms for stochastic combinatorial optimization problems
- An $O(\log \log m)$ Prophet Inequality for Subadditive Combinatorial Auctions
This page was built for publication: Online contention resolution schemes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575652)
