A classic theorem by Vizing asserts that if the maximum degree of a graph is D, then it is possible to color its edges, in polynomial time, using at most D+ 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 D = w(n 2 ), where n is the number of vertices. In this paper, we show that for graphs with D = w(log n), it is possible to color the graph with 1+ e=(e 2 1)+ o(1) D 1:43D 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.
['Bahman Bahmani', 'Aranyak Mehta', 'Rajeev Motwani']
Online Graph Edge-Coloring in the Random-Order Arrival Model