descriptionPublicationkeyboard_double_arrow_right Article , Conference object 01 Jun 2018 English Publisher:World Scientific Pub Co Pte LtJournal:International Journal of Foundations of Computer Science, volume 29, pages 551-569 (issn: 0129-0541, eissn: 1793-6373,

Authors: Burjons Pujol, Elisabet; Hromkovic, Juraj; Kralovic, Rastislav; Kralovic, Richard; Muñoz López, Francisco Javier; Unger, Walter;

doi: 10.1142/s0129054118410058

handle: 2117/177333 , 20.500.11850/274991

Online Graph Coloring Against a Randomized Adversary

- Summary
- Subjects
- Metrics

Abstract

We consider an online model where an adversary constructs a set of [Formula: see text] instances [Formula: see text] instead of one single instance. The algorithm knows [Formula: see text] and the adversary will choose one instance from [Formula: see text] at random to present to the algorithm. We further focus on adversaries that construct sets of [Formula: see text]-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 [Formula: see text] and matching upper and lower bound are given for a specific set of algorithms that we call “minimalistic online algorithms”.

Related Organizations

Comenius University
Slovakia
ETH Zurich
Switzerland
Universitat Polite`cnica de Catalunya
Spain
Google (Switzerland)
Switzerland
Universitat Politècnica de Catalunya
Spain

View all View all

Keywords

Information theory, Programari, Online computation, Informació, :Matemàtiques i estadística::Matemàtica aplicada a les ciències [Àrees temàtiques de la UPC], Classificació AMS::05 Combinatorics::05C Graph theory, Operations research, randomization, Investigació operativa, :68 Computer science::68N Software [Classificació AMS], :Matemàtiques i estadística::Investigació operativa [Àrees temàtiques de la UPC], Classificació AMS::90 Operations research, mathematical programming::90B Operations research and management science, information, Grafs, :90 Operations research, mathematical programming::90B Operations research and management science [Classificació AMS], graph coloring, Àrees temàtiques de la UPC::Matemàtiques i estadística::Investigació operativa, Classificació AMS::68 Computer science::68N Software, Computer software, Classificació AMS::90 Operations research, Teoria de la, Teoria de, Grafs, Teoria de, À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::Matemàtica discreta::Teoria de grafs, 004, Online computation; information; randomization; graph coloring, Graph theory, mathematical programming::90B Operations research and management science, Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica aplicada a les ciències, Informació, Teoria de la, :05 Combinatorics::05C Graph theory [Classificació AMS], :Matemàtiques i estadística::Investigació operativa::Optimització [Àrees temàtiques de la UPC], :Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs [Àrees temàtiques de la UPC]

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	3
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average