Improved Guarantees for Offline Stochastic Matching via New Ordered Contention Resolution Schemes

Matching is one of the most fundamental and broadly applicable problems across many domains. In these diverse real-world applications, there is often a degree of uncertainty in the input, which has led to the study of stochastic matching models. Here, each edge in the graph has a known, independent probability of existing derived from some prediction. Algorithms must probe edges to determine existence and match them irrevocably if they exist. Further, each vertex may have a patience constraint denoting how many of its neighboring edges can be probed. We present new ordered contention resolution schemes yielding improved approximation guarantees for some of the foundational problems studied in this area. For stochastic matching with patience constraints in general graphs, we provide a 0.382-approximate algorithm, significantly improving over the previous best 0.31-approximation. When the vertices do not have patience constraints, we describe a 0.432-approximate random order probing algorithm with several corollaries, such as an improved guarantee for the Prophet Secretary problem under Edge Arrivals. Finally, for the special case of bipartite graphs with unit patience constraints on one of the partitions, we show a 0.632-approximate algorithm that improves on a recent result providing a guarantee of 1/3. Funding: N. Grammel and A. Srinivasan were financially supported in part by the National Science Foundation Division of Computing and Communication Foundations [Award CCF-1749864] and by research awards from Amazon and Google.