|
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:
|
|
