Published: December 9, 2012
Abstract: [Plain Text Version]
A classic theorem by Vizing asserts that if the maximum degree of a graph is $\Delta$, then it is possible to color its edges, in polynomial time, using at most $\Delta+1$ colors. However, this algorithm is offline, i.e., it assumes the whole graph is known in advance. A natural question then is how well we can do in the online setting, where the edges of the graph are revealed one by one, and we need to color each edge as soon as it is added to the graph. Online edge coloring has an important application in fast switch scheduling. A natural model is that edges arrive online, but in a random permutation. Even in the random permutation model, the best proven approximation factor for any algorithm is the factor 2 of the simple greedy algorithm (which holds even in the worst-case online model). The algorithm of Aggarwal et al. (FOCS'03) provides a 1+o(1) factor algorithm for the case of very dense multi-graphs, when $\Delta=\omega(n^{2})$, where $n$ is the number of vertices. In this paper, we show that for graphs with $\Delta=\omega(\log\: n)$, it is possible to color the graph with $\left(1 + \frac{\eee}{\eee^2-1}+o(1)\right)\Delta \leq 1.43\Delta$ colors, with high probability, in the online random-order model. Our algorithm is inspired by a 1.6-approximate distributed offline algorithm of Panconesi and Srinivasan (PODC'92), which we extend by reusing failed colors online.
Further, we show how we can extend the algorithm to reuse colors multiple times, which reduces the approximation factor below 1.43. We conjecture that the algorithm becomes nearly optimal (i.e., uses $\Delta + o(\Delta)$ colors) with $O(\log{(\Delta/\log{n})})$ reuses. We reduce the question to proving the non-negativity of a certain recursively defined sequence, which looks true in computer simulations. This non-negativity can be proved explicitly for a small number of reuses, giving improved algorithms: e.g., the algorithm which reuses colors 5 times uses $1.26\Delta$ colors.
A preliminary version of this paper appeared in the Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010).
Licensed under a Creative Commons Attribution License (CC-BY)