Improved Guarantees for Offline Stochastic Matching via New Ordered Contention Resolution Schemes
Provides better theoretical bounds for stochastic matching, a fundamental problem with applications in online advertising and resource allocation.
The paper improves approximation guarantees for offline stochastic matching with patience constraints, achieving 0.382 (previously 0.31) for general graphs with patience ≥2, 0.432 without patience constraints, and 0.632 for bipartite graphs with unit patience on one side (previously 1/3).
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 assuming each vertex has patience at least $2$. Under this assumption, we improve upon the previous best 0.31-approximation of Baveja et al. (2018). 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 the recent $1/3$-guarantee of Hikima et al. (2021).