Ignorance is Almost Bliss: Near-Optimal Stochastic Matching With Few Queries

Avrim Blum, John P. Dickerson, Nika Haghtalab +3

The stochastic matching problem deals with finding a maximum matching in a graph whose edges are unknown but can be accessed via queries. This is a special case of stochastic $k$-s…