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\"ive greedy algorithm is best possible online. However, their lower bound required bounded-degree graphs, of maximum degree $\Delta = 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 \emph{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 $\Delta = \omega(\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)\cdot x_e$, for a constant $c>0.027$.
翻译:近30年前, Bar-Noy、 Motwani 和 Naor 表示, 任何在线边缘色彩算法都无法优化地显示图表的颜色。 事实上, 他们题为“ 贪婪算法是在线边缘颜色的最佳选择 ” 的作品显示, “ 贪婪算法” 的2美元的竞争性比率是最佳的在线选择。 但是, 他们的下约束要求约束度图, 最大值为$\Delta = O(\log n) $, 这促使他们推测, 高度图形有更好的界限。 虽然在解决限制投入和抵达或随机抵达订单的配方方面已经取得了进展, 但对于完全通用的\emph{对质的到达来说, 答案仍然是难以实现的。 我们用肯定的方式解决了这个三十年的配方的配方, $(1.9+o(1)) 美元 的有竞争力的在线边端算算法 = 美元= 美元= 美元(log n) 的顶值 。 在我们结果的核心, 以及可能的独立利益之下, $= 美元 美元 美元 的顶点 匹配的在线 双平位 。