Online bipartite matching with imperfect advice
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916257123532800 |
|---|---|
| author | Choo, Davin Gouleakis, Themis Ling, Chun Kai Bhattacharyya, Arnab |
| author_facet | Choo, Davin Gouleakis, Themis Ling, Chun Kai Bhattacharyya, Arnab |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_09784 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Online bipartite matching with imperfect advice Choo, Davin Gouleakis, Themis Ling, Chun Kai Bhattacharyya, Arnab Machine Learning Artificial Intelligence Data Structures and Algorithms 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. |
| title | Online bipartite matching with imperfect advice |
| topic | Machine Learning Artificial Intelligence Data Structures and Algorithms |
| url | https://arxiv.org/abs/2405.09784 |