UPCommons. Portal del coneixement obert de la UPC
Publicación
Contribución de congreso (ConferenceOutput)
Online graph coloring with advice and randomized adversary
We generalize the model of online computation with three players (algorithm, adversary and an oracle called advisor) by strength- ening the power of the adversary by randomization. In our generalized model, the advisor knows everything about the adversary except the ran- dom bits the adversary may use.
We examine the expected competitive ratio of online algorithms within this model in order to measure the hardness of online problems in a new way. We start our investigation by proving upper and lower bounds on the competitive ratio for the online graph coloring problem., Peer Reviewed