Publication
We study online bipartite edge coloring, with nodes on one side of the graph revealed sequentially. The trivial greedy algorithm is (2 — o (1))-competitive, which is optimal for graphs of low maximum degree, Δ = O (log n) [BNMN IPL’92]. Numerous online edge-coloring algorithms outperforming the greedy algorithm in various settings were designed over the years (e.g., [AGKM FOCS’03, BMM SODA’10, CPW FOCS’19, BGW SODA’21, KLSST STOC’22, BSVW STOC’24]), all crucially relying on randomization. A commonly- held belief, first stated by [BNMN IPL’92], is that randomization is necessary to outperform greedy. We refute this belief. We present a deterministic algorithm that beats greedy for sufficiently large Δ = Ω(log n ), and in particular has competitive ratio for all Δ = ω (log n ). We obtain our result via a new simple randomized algorithm that works against adaptive adversaries (as opposed to oblivious adversaries assumed by prior work). This implies the existence of a similarly-competitive deterministic algorithm [BDBKTW STOC’90]. A key ingredient in our algorithm (and the reason for its competitive ratio) is the use of contention resolution schemes of [FV FOCS’06]. This is the first use of contention resolution schemes, which are randomized algorithms for randomized inputs, that yields a deterministic algorithm for deterministic settings.