Title:
|
Online graph coloring against a randomized adversary
|
Author:
|
Burjons Pujol, Elisabet; Hromkovic, Juraj; Kralovic, Rastislav; Kralovic, Richard; Muñoz López, Francisco Javier; Unger, Walter
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament de Matemàtiques; Universitat Politècnica de Catalunya. COMBGRAPH - Combinatòria, Teoria de Grafs i Aplicacions |
Abstract:
|
Electronic version of an article published as
Online graph coloring against a randomized adversary. "International journal of foundations of computer science", 1 Juny 2018, vol. 29, núm. 4, p. 551-569. DOI:10.1142/S0129054118410058 © 2018 copyright World Scientific Publishing Company. https://www.worldscientific.com/doi/abs/10.1142/S0129054118410058 |
Abstract:
|
We consider an online model where an adversary constructs a set of 2s instances S instead of one single instance. The algorithm knows S and the adversary will choose one instance from S at random to present to the algorithm. We further focus on adversaries that construct sets of k-chromatic instances. In this setting, we provide upper and lower bounds on the competitive ratio for the online graph coloring problem as a function of the parameters in this model. Both bounds are linear in s and matching upper and lower bound are given for a specific set of algorithms that we call “minimalistic online algorithms”. |
Abstract:
|
Peer Reviewed |
Subject(s):
|
-Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs -Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica aplicada a les ciències -Àrees temàtiques de la UPC::Matemàtiques i estadística::Investigació operativa::Optimització -Àrees temàtiques de la UPC::Matemàtiques i estadística::Investigació operativa -Graph theory -Computer software -Operations research -Information theory -Online computation -information -randomization -graph coloring -Grafs, Teoria de -Programari -Investigació operativa -Informació, Teoria de la -Classificació AMS::05 Combinatorics::05C Graph theory -Classificació AMS::68 Computer science::68N Software -Classificació AMS::90 Operations research, mathematical programming::90B Operations research and management science |
Rights:
|
|
Document type:
|
Article - Submitted version Article |
Share:
|
|