Online Stochastic Matching: Online Actions Based on Offline Statistics

DOI10.1287/moor.1120.0551zbMath1297.68269arXiv1007.1673MaRDI QIDQ2925346

Shayan Oveis Gharan, Amin Saberi, V. H. Manshadi

Publication date: 21 October 2014

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1007.1673

zbMATH Keywords

stochastic optimization; online bipartite matching; optimum offline estimation; rounding by sampling

Mathematics Subject Classification ID

68W40: Analysis of algorithms

05C90: Applications of graph theory

90C27: Combinatorial optimization

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68W20: Randomized algorithms

68W27: Online algorithms; streaming algorithms