|
| | | | |
| | | |
| Stat |
Members: 3667
Articles: 2'599'751
Articles rated: 2609
07 February 2025 |
|
| | | | |
|
Article overview
| |
|
|
Online Contention Resolution Schemes | | Moran Feldman
; Ola Svensson
; Rico Zenklusen
; | | Date: |
1 Aug 2015 | | 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. | | Source: | arXiv, 1508.0142 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|
REGISTER