Improved Approximations for Stationary Bipartite Matching: Beyond Probabilistic Independence
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915016596258816 |
|---|---|
| author | AmaniHamedani, Alireza Aouad, Ali Pollner, Tristan Saberi, Amin |
| author_facet | AmaniHamedani, Alireza Aouad, Ali Pollner, Tristan Saberi, Amin |
| contents | We study stationary online bipartite matching, where both types of nodes--offline and online--arrive according to Poisson processes. Offline nodes wait to be matched for some random time, determined by an exponential distribution, while online nodes need to be matched immediately. This model captures scenarios such as deceased organ donation and time-sensitive task assignments, where there is an inflow of patients and workers (offline nodes) with limited patience, while organs and tasks (online nodes) must be assigned upon arrival.
We present an efficient online algorithm that achieves a $(1-1/e+δ)$-approximation to the optimal online policy's reward for a constant $δ> 0$, simplifying and improving previous work by Aouad and Saritaç (2022). Our solution combines recent online matching techniques, particularly pivotal sampling, which enables correlated rounding of tighter linear programming approximations, and a greedy-like algorithm. A key technical component is the analysis of a stochastic process that exploits subtle correlations between offline nodes, using renewal theory. A byproduct of our result is an improvement to the best-known competitive ratio--that compares an algorithm's performance to the optimal offline policy--via a $(1-1/\sqrt{e} + η)$-competitive algorithm for a universal constant $η> 0$, advancing the results of Patel and Wajc (2024). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_08218 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Improved Approximations for Stationary Bipartite Matching: Beyond Probabilistic Independence AmaniHamedani, Alireza Aouad, Ali Pollner, Tristan Saberi, Amin Data Structures and Algorithms 68W27 G.3; F.2 We study stationary online bipartite matching, where both types of nodes--offline and online--arrive according to Poisson processes. Offline nodes wait to be matched for some random time, determined by an exponential distribution, while online nodes need to be matched immediately. This model captures scenarios such as deceased organ donation and time-sensitive task assignments, where there is an inflow of patients and workers (offline nodes) with limited patience, while organs and tasks (online nodes) must be assigned upon arrival. We present an efficient online algorithm that achieves a $(1-1/e+δ)$-approximation to the optimal online policy's reward for a constant $δ> 0$, simplifying and improving previous work by Aouad and Saritaç (2022). Our solution combines recent online matching techniques, particularly pivotal sampling, which enables correlated rounding of tighter linear programming approximations, and a greedy-like algorithm. A key technical component is the analysis of a stochastic process that exploits subtle correlations between offline nodes, using renewal theory. A byproduct of our result is an improvement to the best-known competitive ratio--that compares an algorithm's performance to the optimal offline policy--via a $(1-1/\sqrt{e} + η)$-competitive algorithm for a universal constant $η> 0$, advancing the results of Patel and Wajc (2024). |
| title | Improved Approximations for Stationary Bipartite Matching: Beyond Probabilistic Independence |
| topic | Data Structures and Algorithms 68W27 G.3; F.2 |
| url | https://arxiv.org/abs/2411.08218 |