On (Random-Order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs

The first author thanks Patrick Bennett for suggesting the critical interval approach used to complete the proof of Proposition 14 in the conference version of the paper. The second author thanks Joey Huchette for suggesting to use the COUENNE package with JuMP. The authors thank all anonymous reviewers for SODA and Operations Research, in particular, the one who suggested the simpler 1-regularity reduction that is currently presented to prove Lemma EC.1. An earlier version of this work appeared in the ACM-SIAM Symposium on Discrete Algorithms (SODA) (MacRury et al. 2023), where a 0.4761 lower bound on RCRS selectability for bipartite graphs was presented. We improved this to 0.4789 in this version.