论文标题
通过nibble方法在线边缘着色算法
Online Edge Coloring Algorithms via the Nibble Method
论文作者
论文摘要
大约30年前，Bar-Noy，Motwani和Naor [IPL'92]猜想，在线$（1+O（1））δ$ - 边缘色算法的最高度$δ=ω（\ log n）$的$ n $ node图的存在。该猜想一般仍然是开放的，尽管最近在\ emph（Cohen et al。[focs'19]的\ emph {单方面顶点到达}下，这是对两部分图的证明。同样，我们研究了在线模型的广泛研究下的边缘着色。 我们的主要结果是\ emph {Random-Order}在线模型。对于此模型，已知的结果未达到Bar-Noy等人的猜测，无论是在Aggarwal等人[Aggarwal等〜focs'03]或所使用的颜色数量[Bahmani等人〜Soda'10]中。我们在两全其美的情况下取得了最好的成绩，从而解决了该模型的肯定中的Bar-Noy等人。 我们的第二个结果是在\ emph {rocerulte}的对抗性（和动态）模型中。 Duan等人的最新算法〜[SODA'19]产生了$（1+ε）δ$ - edge-edge-edge-ended-edge-edgoloing poly $（\ log n/ε）$ rockiress。我们使用poly $（1/ε）$ rockiress实现了同样的成就，从而消除了对$ n $的全部依赖。 我们的结果的基础是一种常见的离线算法，我们将在这两个在线模型中展示如何实施。我们的算法基于RödlNibble方法，是Dubhashi等人的分布算法的适应。 Nibble方法已被证明成功地用于分布式边缘着色。我们在在线算法的背景下显示其有用性。
Nearly thirty years ago, Bar-Noy, Motwani and Naor [IPL'92] conjectured that an online $(1+o(1))Δ$-edge-coloring algorithm exists for $n$-node graphs of maximum degree $Δ=ω(\log n)$. This conjecture remains open in general, though it was recently proven for bipartite graphs under \emph{one-sided vertex arrivals} by Cohen et al.~[FOCS'19]. In a similar vein, we study edge coloring under widely-studied relaxations of the online model. Our main result is in the \emph{random-order} online model. For this model, known results fall short of the Bar-Noy et al.~conjecture, either in the degree bound [Aggarwal et al.~FOCS'03], or number of colors used [Bahmani et al.~SODA'10]. We achieve the best of both worlds, thus resolving the Bar-Noy et al.~conjecture in the affirmative for this model. Our second result is in the adversarial online (and dynamic) model with \emph{recourse}. A recent algorithm of Duan et al.~[SODA'19] yields a $(1+ε)Δ$-edge-coloring with poly$(\log n/ε)$ recourse. We achieve the same with poly$(1/ε)$ recourse, thus removing all dependence on $n$. Underlying our results is one common offline algorithm, which we show how to implement in these two online models. Our algorithm, based on the Rödl Nibble Method, is an adaptation of the distributed algorithm of Dubhashi et al.~[TCS'98]. The Nibble Method has proven successful for distributed edge coloring. We display its usefulness in the context of online algorithms.
