In this STSM, Aris Anagnostopoulos, who is a Marie-Curie Fellow at

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.

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.