Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities
Christos H. Papadimitriou, Tristan Pollner, Amin Saberi, David Wajc
Abstract
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?
Topics & Concepts
Benchmark (surveying)Bipartite graphMatching (statistics)Online algorithmComputer scienceTime complexitySelection (genetic algorithm)Computational complexity theoryBayesian probabilityInequalityArtificial intelligenceAlgorithmMathematicsMathematical optimizationTheoretical computer scienceStatisticsGeodesyMathematical analysisGraphGeographyOptimization and Search ProblemsAdvanced Bandit Algorithms ResearchMachine Learning and Algorithms