Back to Search Start Over

Online Bipartite Matching with Reusable Resources.

Online Bipartite Matching with Reusable Resources.

Authors :
Delong, Steven
Farhadi, Alireza
Niazadeh, Rad
Sivan, Balasubramanian
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