On (Random-Order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs
研究在线争用解决机制在图匹配约束下的表现，考虑对抗顺序和随机顺序、二分图与一般图四种情形，改进了算法保证和不可能性结果，适用于在线资源分配和随机优化问题。
Online Contention Resolution Schemes for the Matching Polytope of Graphs Online contention resolution schemes (OCRSs) are used to select a subset of elements, subject to feasibility constraints. Originally developed as a randomized rounding tool for constrained submodular optimization, OCRSs have found numerous applications in online resource allocation and stochastic optimization. This includes problems such as prophet inequalities, stochastic probing, auction design, and matching in a gig economy. In “On (Random-Order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs,” Calum MacRury, Will Ma, and Nathaniel Grammel study OCRSs when the feasibility constraints are defined by graph matchings. The authors consider when the elements are sequentially presented in adversarial or random order, as well as when the graph is bipartite or general. In each combination of variants, the authors improve the state of the art, both in terms of algorithmic guarantees and impossibility results.