Randomized path coloring on binary trees

AbstractMotivated by the problem of WDM routing in all-optical networks, we study the following NP-hard problem. We are given a directed binary tree T and a set R of directed paths on T. We wish to assign colors to paths of R, in such way that no two paths that share a directed arc of T are assigned the same color, and the total number of colors used is minimized. Our results are expressed in terms of the depth of the tree and of the maximum load l of R, i.e. the maximum number of paths that go through a directed arc of T. So far, only deterministic greedy algorithms have been presented for the problem. The best known algorithm colors any set R of maximum load l using at most 5l/3 colors. Alternatively, we say that this algorithm has performance ratio 53. It is also known that no deterministic greedy algorithm can achieve a performance ratio better than 53. In this paper we define the class of greedy algorithms that use randomization. We study their limitations and prove that, with high probability, randomized greedy algorithms cannot achieve a performance ratio better than 32 when applied for binary trees of depth Ω(l), and 1.293−o(1) when applied for binary trees of constant depth. Exploiting inherent properties of randomized greedy algorithms, we obtain the first randomized algorithm for the problem that uses at most 7l/5+o(l) colors for coloring any set of paths of maximum load l on binary trees of depth O(l1/3−ε), with high probability. We also present an existential upper bound of 7l/5+o(l) that holds on any binary tree. For the analysis of our bounds we develop tail inequalities for random variables following hypergeometrical probability distributions that might be of their own interest