Theorem 2.7, p. 13 — the degree relaxation of matching has a (b, e^{−2b})-selectable randomized greedy OCRS
ProvedOnlineCRS.Matching.matching_ocrsLet be a finite graph without loops, and let
be the degree relaxation of matching, where is the set of edges at . For every there exists a randomized greedy OCRS for , whose families consist of matchings, that is -selectable: for every and every edge ,
Since every element is then selected with probability at least when active, against any arrival order, this gives a constant-factor online rounding for matchings in general graphs; as contains the matching polytope, the result applies to it as well.
Formalization Note The scheme is a probability distribution on families of edge sets, for every , supported on down-closed families of matchings containing ; probabilities are finite sums of product weights. The graph is the published EdmondsMatching65.Polyhedron.Graph (loopless; parallel edges allowed, a harmless generalization of the paper's graph). Selectability is required for every edge, including edges with .
import Mathlib import Definitions.Def_OnlineCRS_Matching_Model
namespace OnlineCRS.Matching
/-- Theorem 2.7, p. 13: the degree relaxation of matching admits a randomized greedy OCRS. -/
theorem matching_ocrs {V E : Type} [Fintype V] [DecidableEq V]
[Fintype E] [DecidableEq E] (G : EdmondsMatching65.Polyhedron.Graph V E)
(b : ℝ) (hb0 : 0 ≤ b) (hb1 : b ≤ 1) :
∃ w : (E → ℝ) → Finset (Finset E) → ℝ,
OnlineCRS.Matroid.IsSelectableRand (EdmondsMatching65.Polyhedron.IsMatching G) (matchingRelax G) b
(Real.exp (-2 * b)) w := by sorry
end OnlineCRS.Matching
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.