Lemma 5 — RANKING produces at least as large a matching as EARLY
ProvedKVVMatching.Ranking.lemma_5bipartite-matchingonline-algorithmsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix an upper-triangular adjacency matrix with unit diagonal and any ordering of its rows. RANKING matches each arriving row to the highest-ranked eligible column. EARLY follows the same rule except that it refuses row when its own matching has already covered column . For this fixed order,
This is a pointwise comparison for every row order, before taking any expectation.
Preamble
import Definitions.Def_KVVMatching_Ranking_Algorithms
Formal statement
namespace KVVMatching.Ranking
/-- Lemma 5, p. 354: RANKING's matching is at least as large as EARLY's. -/
theorem lemma_5 {n : ℕ} (adj : Fin n → Fin n → Prop)
(hdiag : ∀ i, adj i i)
(hupper : ∀ i j, adj i j → i ≤ j)
(rowOrder : Equiv.Perm (Fin n)) :
(earlyMatching adj rowOrder).card ≤ (rowRankingMatching adj rowOrder).card := by sorry
end KVVMatching.Ranking
Source
Karp, Vazirani, Vazirani, An Optimal Algorithm for On-line Bipartite Matching, STOC 1990, p. 354, EARLY definition and Lemma 5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.