Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities
Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities
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., …