Key points are not available for this paper at this time.
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.
Papadimitriou et al. (Thu,) studied this question.