Pasar al contenido principal

OPTIMIZACION Y PROBLEMAS EXTREMALES EN TEORIA DE GRAFOS Y COMBINATORIA. APLICACIONES A LAS REDES DE COMUNICACION.

MTM2011-28800-C02-01

•
Nombre agencia financiadora Ministerio de Ciencia e Innovación
Acrónimo agencia financiadora MICINN
Programa Programa Nacional de Proyectos de Investigación Fundamental
Subprograma Subprograma de Proyectos de Investigación Fundamental no Orientada
Convocatoria Proyectos I+D
Año convocatoria 2011
Plan Estatal 2008-2011 Plan Nacional de Investigación Científica, Desarrollo e Innovación Tecnológica
Unidad de gestión Subdirección General de Proyectos de Investigación
Centro beneficiario UNIVERSITAT POLITECNICA DE CATALUNYA
Identificador persistente http://dx.doi.org/10.13039/501100004837

Resultados relacionados

Resultados totales (Incluyendo duplicados): 2
Encontrada(s) 1 página(s)

UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Online graph coloring with advice and randomized adversary

  • Muñoz López, Francisco Javier|||0000-0002-2560-3540
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
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Online graph coloring with advice and randomized adversary

  • Muñoz López, Francisco Javier
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, Postprint (author's final draft)