Online bipartite matching with imperfect advice

Davin Choo, Themistoklis Gouleakis, Chun Kai Ling, Arnab Bhattacharyya
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:8762-8781, 2024.

Abstract

We study the problem of online unweighted bipartite matching with $n$ offline vertices and $n$ online vertices where one wishes to be competitive against the optimal offline algorithm. While the classic RANKING algorithm of (Karp et al., 1990) provably attains competitive ratio of $1-1/e > 1/2$, we show that no learning-augmented method can be both 1-consistent and strictly better than 1/2-robust under the adversarial arrival model. Meanwhile, under the random arrival model, we show how one can utilize methods from distribution testing to design an algorithm that takes in external advice about the online vertices and provably achieves competitive ratio interpolating between any ratio attainable by advice-free methods and the optimal ratio of 1, depending on the advice quality.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-choo24a, title = {Online bipartite matching with imperfect advice}, author = {Choo, Davin and Gouleakis, Themistoklis and Ling, Chun Kai and Bhattacharyya, Arnab}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {8762--8781}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/choo24a/choo24a.pdf}, url = {https://proceedings.mlr.press/v235/choo24a.html}, abstract = {We study the problem of online unweighted bipartite matching with $n$ offline vertices and $n$ online vertices where one wishes to be competitive against the optimal offline algorithm. While the classic RANKING algorithm of (Karp et al., 1990) provably attains competitive ratio of $1-1/e > 1/2$, we show that no learning-augmented method can be both 1-consistent and strictly better than 1/2-robust under the adversarial arrival model. Meanwhile, under the random arrival model, we show how one can utilize methods from distribution testing to design an algorithm that takes in external advice about the online vertices and provably achieves competitive ratio interpolating between any ratio attainable by advice-free methods and the optimal ratio of 1, depending on the advice quality.} }
Endnote
%0 Conference Paper %T Online bipartite matching with imperfect advice %A Davin Choo %A Themistoklis Gouleakis %A Chun Kai Ling %A Arnab Bhattacharyya %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-choo24a %I PMLR %P 8762--8781 %U https://proceedings.mlr.press/v235/choo24a.html %V 235 %X We study the problem of online unweighted bipartite matching with $n$ offline vertices and $n$ online vertices where one wishes to be competitive against the optimal offline algorithm. While the classic RANKING algorithm of (Karp et al., 1990) provably attains competitive ratio of $1-1/e > 1/2$, we show that no learning-augmented method can be both 1-consistent and strictly better than 1/2-robust under the adversarial arrival model. Meanwhile, under the random arrival model, we show how one can utilize methods from distribution testing to design an algorithm that takes in external advice about the online vertices and provably achieves competitive ratio interpolating between any ratio attainable by advice-free methods and the optimal ratio of 1, depending on the advice quality.
APA
Choo, D., Gouleakis, T., Ling, C.K. & Bhattacharyya, A.. (2024). Online bipartite matching with imperfect advice. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:8762-8781 Available from https://proceedings.mlr.press/v235/choo24a.html.

Related Material