EUVIMEDEUVIMED entdecken
Crossref

Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities

Christos Papadimitriou, Tristan Pollner, Amin Saberi, David Wajc

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →