Online Stochastic Matching: Online Actions Based on Offline Statistics
Manshadi V, Gharan S, Saberi A. Online Stochastic Matching: Online Actions Based on Offline Statistics. Mathematics Of Operations Research 2012, 37: 559-573. DOI: 10.1287/moor.1120.0551.Peer-Reviewed Original ResearchCompetitive ratioOnline algorithmOnline stochastic matching problemStochastic matching problemOptimum offline solutionBipartite graphsHardness resultsPermutation modelMonte Carlo samplingMatching problemHard sideAd allocationEmpty binsOffline solutionGraphOffline statisticsAlgorithmOnline actionsBallPermutationProblemAllocationBall typeMonteBins