In this STSM, Aris Anagnostopoulos, who is a Marie-Curie
the Department of Informatics and System Sciences at the Sapienza
University of Rome, Italy, visited the Computer Engineering and
Informatics Department at the University of Patras, Greece from
November 29 to December 19, 2010. The host was Prof. Ioannis
Caragiannis. We studied online graph coloring on trees.
Online graph coloring problems have important applications in resource
allocation problems such as frequency assignment in wireless networks.
During this STSM we worked on online coloring of trees. In an online
setting the input of the problem is not known in advance but it is
revealed gradually. Whenever part of the input is revealed, the online
algorithm must make an irrevocable decision based on the part of the
input that has been revealed. Our objective is to design algorithms that
are competitive in the sense that the solutions obtained have cost close
to the optimal cost for the given instance. Note that the limitations of
algorithms in this setting are due to the fact that algorithms cannot
predict the future.
In the online coloring of trees the nodes of a tree graph appear online.
When a node appears, the edges adjacent to the node and nodes appeared
previously are revealed as well. An online coloring algorithm has to
assign a color to the node which is different than the colors already
assigned to its neighbors. The objective of the algorithm is to minimize
the total number of colors used. The optimal deterministic algorithm
uses O(log n) more colors than the optimal coloring (where n is the
number of nodes),
While deterministic algorithms have been studied extensively for
online coloring of trees for many years, the power of randomization has
not been yet understood. For example the lower bound of the order of logn
for deteterministic algorithms cannot be applied to randomized
algorithms. We studied a variety of randomized algorithms for the problem
and we proved that neither randomized algorithms can achieve an optimal
online performance. Precisely, the competitive ratio for any randomized
algorithm is lower bounded by O(log n/log log n). An interesting open
question of our research is whether there exists a randomized algorithm
able to achieve this performance.