Skip to main content

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

MTM2011-28800-C02-01

•
Funding agency name Ministerio de Ciencia e Innovación
Funding agency acronym MICINN
Program Programa Nacional de Proyectos de Investigación Fundamental
Subprogram Subprograma de Proyectos de Investigación Fundamental no Orientada
Call Proyectos I+D
Call year 2011
State Plan 2008-2011 Plan Nacional de Investigación Científica, Desarrollo e Innovación Tecnológica
Management unit Subdirección General de Proyectos de Investigación
Beneficiary centre UNIVERSITAT POLITECNICA DE CATALUNYA

Resultados relacionados

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

UPCommons. Portal del coneixement obert de la UPC
Publication 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
Publication 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)