Approximating Optimum Online for Capacitated Resource Allocation
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909222181011456 |
|---|---|
| author | Braun, Alexander Kesselheim, Thomas Pollner, Tristan Saberi, Amin |
| author_facet | Braun, Alexander Kesselheim, Thomas Pollner, Tristan Saberi, Amin |
| contents | We study online capacitated resource allocation, a natural generalization of online stochastic max-weight bipartite matching. This problem is motivated by ride-sharing and Internet advertising applications, where online arrivals may have the capacity to serve multiple offline users.
Our main result is a polynomial-time online algorithm which is $(1/2 + κ)$-approximate to the optimal online algorithm for $κ= 0.0115$. This can be contrasted to the (tight) $1/2$-competitive algorithms to the optimum offline benchmark from the prophet inequality literature. Optimum online is a recently popular benchmark for online Bayesian problems which can use unbounded computation, but not "prophetic" knowledge of future inputs.
Our algorithm (which also works for the case of stochastic rewards) rounds a generalized LP relaxation from the unit-capacity case via a two-proposal algorithm, as in previous works in the online matching literature. A key technical challenge in deriving our guarantee is bounding the positive correlation among users introduced when rounding our LP relaxation online. Unlike in the case of unit capacities, this positive correlation is unavoidable for guarantees beyond $1/2$. Conceptually, our results show that the study of optimum online as a benchmark can reveal problem-specific insights that are irrelevant to competitive analysis. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_07757 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Approximating Optimum Online for Capacitated Resource Allocation Braun, Alexander Kesselheim, Thomas Pollner, Tristan Saberi, Amin Data Structures and Algorithms We study online capacitated resource allocation, a natural generalization of online stochastic max-weight bipartite matching. This problem is motivated by ride-sharing and Internet advertising applications, where online arrivals may have the capacity to serve multiple offline users. Our main result is a polynomial-time online algorithm which is $(1/2 + κ)$-approximate to the optimal online algorithm for $κ= 0.0115$. This can be contrasted to the (tight) $1/2$-competitive algorithms to the optimum offline benchmark from the prophet inequality literature. Optimum online is a recently popular benchmark for online Bayesian problems which can use unbounded computation, but not "prophetic" knowledge of future inputs. Our algorithm (which also works for the case of stochastic rewards) rounds a generalized LP relaxation from the unit-capacity case via a two-proposal algorithm, as in previous works in the online matching literature. A key technical challenge in deriving our guarantee is bounding the positive correlation among users introduced when rounding our LP relaxation online. Unlike in the case of unit capacities, this positive correlation is unavoidable for guarantees beyond $1/2$. Conceptually, our results show that the study of optimum online as a benchmark can reveal problem-specific insights that are irrelevant to competitive analysis. |
| title | Approximating Optimum Online for Capacitated Resource Allocation |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2406.07757 |