Name
Abstract | ||
|---|---|---|
We revisit the fully online matching model (Huang et al., 2020), an extension of the classic online matching model due to Karp, Vazirani, and Vazirani (1990), which has recently received a lot of attention (Huang et al., 2019, 2020), partly due to applications in ride-sharing platforms. It has been shown that the fully online version is harder than the classic version for which the achievable competitive ratio is at most 0.6317, rather than precisely 1 - 1/e approximate to 0.6321. We introduce two new ideas to the construction. By optimizing the parameters of the modified construction numerically, we obtain an improved impossibility result of 0.6297. Like the previous bound, the new bound even holds for fractional (rather than randomized) algorithms on bipartite graphs. (C) 2021 Elsevier B.V. All rights reserved. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1016/j.orl.2021.08.012 | OPERATIONS RESEARCH LETTERS |
Keywords | DocType | Volume |
Online algorithms, Competitive analysis, Matching theory | Journal | 49 |
Issue | ISSN | Citations |
5 | 0167-6377 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alexander Eckl | 1 | 0 | 0.34 |
| Anja Kirschbaum | 2 | 0 | 0.34 |
| Marilena Leichter | 3 | 0 | 0.34 |
| Kevin Schewior | 4 | 0 | 0.34 |