Advice Complexity and Barely Random Algorithms

Komm, Dennis, and Královič, Richard. "Advice Complexity and Barely Random Algorithms." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 45.2 (2011): 249-267. <http://eudml.org/doc/273054>.

@article{Komm2011,
abstract = {Recently, a new measurement – the advice complexity – was introduced for measuring the information content of online problems. The aim is to measure the bitwise information that online algorithms lack, causing them to perform worse than offline algorithms. Among a large number of problems, a well-known scheduling problem, job shop scheduling with unit length tasks, and the paging problem were analyzed within this model. We observe some connections between advice complexity and randomization. Our special focus goes to barely random algorithms, i.e., randomized algorithms that use only a constant number of random bits, regardless of the input size. We adapt the results on advice complexity to obtain efficient barely random algorithms for both the job shop scheduling and the paging problem. Furthermore, so far, it has not yet been investigated for job shop scheduling how good an online algorithm may perform when only using a very small (e.g., constant) number of advice bits. In this paper, we answer this question by giving both lower and upper bounds, and also improve the best known upper bound for optimal algorithms.},
author = {Komm, Dennis, Královič, Richard},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {barely random algorithms; advice complexity; information content; online problems},
language = {eng},
number = {2},
pages = {249-267},
publisher = {EDP-Sciences},
title = {Advice Complexity and Barely Random Algorithms},
url = {http://eudml.org/doc/273054},
volume = {45},
year = {2011},
}

TY - JOUR
AU - Komm, Dennis
AU - Královič, Richard
TI - Advice Complexity and Barely Random Algorithms
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2011
PB - EDP-Sciences
VL - 45
IS - 2
SP - 249
EP - 267
AB - Recently, a new measurement – the advice complexity – was introduced for measuring the information content of online problems. The aim is to measure the bitwise information that online algorithms lack, causing them to perform worse than offline algorithms. Among a large number of problems, a well-known scheduling problem, job shop scheduling with unit length tasks, and the paging problem were analyzed within this model. We observe some connections between advice complexity and randomization. Our special focus goes to barely random algorithms, i.e., randomized algorithms that use only a constant number of random bits, regardless of the input size. We adapt the results on advice complexity to obtain efficient barely random algorithms for both the job shop scheduling and the paging problem. Furthermore, so far, it has not yet been investigated for job shop scheduling how good an online algorithm may perform when only using a very small (e.g., constant) number of advice bits. In this paper, we answer this question by giving both lower and upper bounds, and also improve the best known upper bound for optimal algorithms.
LA - eng
KW - barely random algorithms; advice complexity; information content; online problems
UR - http://eudml.org/doc/273054
ER -