Back to Search
Start Over
Online Bipartite Matching with Reusable Resources.
Online Bipartite Matching with Reusable Resources.
- Source :
- EC: Economics & Computation; 2022, p962-963, 2p
- Publication Year :
- 2022
-
Abstract
- We study the classic online bipartite matching problem with a twist: offline nodes are reusable any number of times. Every offline node i becomes available d steps after it was assigned to. Nothing better than a 0.5-approximation, obtained by the trivial deterministic greedy algorithm, was known for this problem. We give the first approximation factor beating 0.5, namely a 0.505 approximation, by suitably adapting and interpreting the powerful technique of Online Correlated Selection. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- Database :
- Complementary Index
- Journal :
- EC: Economics & Computation
- Publication Type :
- Conference
- Accession number :
- 174692272
- Full Text :
- https://doi.org/10.1145/3490486.3538328