Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities
Mathematics of Operations Research · 2024-08 · 49 (3) · 1607-1628
DOI: 10.1287/moor.2023.1389 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematics of Operations Research, 2024-08. Verfasst von Christos Papadimitriou und 3 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 27 Literaturangaben.
Abstract (Originalsprache)
The rich literature on online Bayesian selection problems has long focused on so-called prophet inequalities, which compare the gain of an online algorithm to that of a “prophet” who knows the future. An equally natural, though significantly less well-studied, benchmark is the optimum online algorithm, which may be omnipotent (i.e., computationally unbounded), but not omniscient. What is the computational complexity of the optimum online? How well can a polynomial-time algorithm approximate it? Motivated by applications in ride hailing, we study the above questions for the online stochastic maximum-weight matching problem under vertex arrivals. For this problem, a number of [Formula: see text]-competitive algorithms are known. This is the best possible ratio for this problem, as it generalizes the original single-item prophet inequality problem. We present a polynomial-time algorithm, which approximates the optimal online algorithm within a factor of 0.51—strictly more than the best-possible constant against a prophet. In contrast, we show that it is PSPACE-hard to approximate this problem within some universal constant [Formula: see text]. Funding: Financial support from the National Science Foundation [Grants CCF1763970, CCF1812919, and CCF191070], the Office of Naval Research [Grant N000141912550], and Cisco Research is gratefully acknowledged.
Zitieren
APA
Papadimitriou, C., Pollner, T., Saberi, A., & Wajc, D. (2024). Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities. Mathematics of Operations Research, 49(3), 1607-1628. https://doi.org/10.1287/moor.2023.1389
Vancouver
Papadimitriou C, Pollner T, Saberi A, Wajc D. Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities. Mathematics of Operations Research. 2024;49(3):1607-1628. doi:10.1287/moor.2023.1389
BibTeX
@article{Papadimitriou2024,
author = {Papadimitriou, Christos and Pollner, Tristan and Saberi, Amin and Wajc, David},
title = {Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities},
journal = {Mathematics of Operations Research},
year = {2024},
volume = {49},
number = {3},
pages = {1607--1628},
doi = {10.1287/moor.2023.1389}
}
EUVIMED