2026-07-22T06:50:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14178 2024-03-06T10:53:40Z ddc:004 open_access

The Greedy Algorithm Is not Optimal for On-Line Edge Coloring Saberi, Amin Wajc, David Online algorithms edge coloring greedy online matching Nearly three decades ago, Bar-Noy, Motwani and Naor showed that no online edge-coloring algorithm can edge color a graph optimally. Indeed, their work, titled "the greedy algorithm is optimal for on-line edge coloring", shows that the competitive ratio of 2 of the naïve greedy algorithm is best possible online. However, their lower bound required bounded-degree graphs, of maximum degree Δ = O(log n), which prompted them to conjecture that better bounds are possible for higher-degree graphs. While progress has been made towards resolving this conjecture for restricted inputs and arrivals or for random arrival orders, an answer for fully general adversarial arrivals remained elusive. We resolve this thirty-year-old conjecture in the affirmative, presenting a (1.9+o(1))-competitive online edge coloring algorithm for general graphs of degree Δ = ω(log n) under vertex arrivals. At the core of our results, and of possible independent interest, is a new online algorithm which rounds a fractional bipartite matching x online under vertex arrivals, guaranteeing that each edge e is matched with probability (1/2+c)⋅ x_e, for a constant c > 0.027. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amin Saberi and David Wajc 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.109 urn:nbn:de:0030-drops-141786 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.109 eng https://creativecommons.org/licenses/by/4.0/legalcode