Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities

• 成果类型: Article
• 署名作者: Papadimitriou, Christos; Pollner, Tristan; Saberi, Amin; Wajc, David
• 署名单位: Columbia University; Stanford University; Alphabet Inc.; Google Incorporated
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2023.1389
• 发表日期: 2024
• 关键词: Approximation; complexity; hardness

摘要

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 wellstudied, 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 1/2-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 polynomialtime 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 & alpha; < 1.