@online{Blikstad2408.03661,
TITLE = {Deterministic Online Bipartite Edge Coloring},
AUTHOR = {Blikstad, Joakim and Svensson, Ola and Vintan, Radu and Wajc, David},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2408.03661},
EPRINT = {2408.03661},
EPRINTTYPE = {arXiv},
YEAR = {2024},
MARGINALMARK = {$\bullet$},
ABSTRACT = {We study online bipartite edge coloring, with nodes on one side of the graph<br>revealed sequentially. The trivial greedy algorithm is $(2-o(1))$-competitive,<br>which is optimal for graphs of low maximum degree, $\Delta=O(\log n)$ [BNMN<br>IPL'92]. Numerous online edge-coloring algorithms outperforming the greedy<br>algorithm in various settings were designed over the years (e.g., AGKM FOCS'03,<br>BMM SODA'10, CPW FOCS'19, BGW SODA'21, KLSST STOC'22, BSVW STOC'24), all<br>crucially relying on randomization. A commonly-held belief, first stated by<br>[BNMN IPL'92], is that randomization is necessary to outperform greedy.<br> Surprisingly, we refute this belief, by presenting a deterministic algorithm<br>that beats greedy for sufficiently large $\Delta=\Omega(\log n)$, and in<br>particular has competitive ratio $\frac{e}{e-1}+o(1)$ for all<br>$\Delta=\omega(\log n)$. We obtain our result via a new and surprisingly simple<br>randomized algorithm that works against adaptive adversaries (as opposed to<br>oblivious adversaries assumed by prior work), which implies the existence of a<br>similarly-competitive deterministic algorithm [BDBKTW STOC'90].<br>},
}