|
Título:
|
Online graph coloring with advice and randomized adversary
|
|
Autor/a:
|
Muñoz López, Francisco Javier
|
|
Otros autores:
|
Universitat Politècnica de Catalunya. Departament de Matemàtiques; Universitat Politècnica de Catalunya. COMBGRAPH - Combinatòria, Teoria de Grafs i Aplicacions |
|
Abstract:
|
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. |
|
Abstract:
|
Peer Reviewed |
|
Materia(s):
|
-Àrees temàtiques de la UPC::Matemàtiques i estadística::Investigació operativa::Programació matemàtica
-Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica aplicada a les ciències
-Programming (Mathematics)
-Computer architecture
-Online computation · Information · Randomization · Graph coloring
-Programació (Matemàtica)
-Arquitectura d'ordinadors
-Classificació AMS::90 Operations research, mathematical programming::90C Mathematical programming
-Classificació AMS::68 Computer science::68M Computer system organization |
|
Derechos:
|
|
|
Tipo de documento:
|
Artículo - Versión presentada
Objeto de conferencia |
|
Editor:
|
Springer
|
|
Compartir:
|
|
