تقرير
Online bipartite matching with imperfect advice
| العنوان: | Online bipartite matching with imperfect advice |
|---|---|
| المؤلفون: | Choo, Davin, Gouleakis, Themis, Ling, Chun Kai, Bhattacharyya, Arnab |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science Statistics |
| مصطلحات موضوعية: | Computer Science - Machine Learning, Computer Science - Artificial Intelligence, Computer Science - Data Structures and Algorithms, Statistics - Machine Learning |
| الوصف: | 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. Comment: Accepted into ICML 2024 |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2405.09784 |
| رقم الأكسشن: | edsarx.2405.09784 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |