Voir la notice de l'article provenant de la source Numdam
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.
@article{ITA_2011__45_2_249_0,
author = {Komm, Dennis and Kr\'alovi\v{c}, Richard},
title = {Advice {Complexity} and {Barely} {Random} {Algorithms}},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {249--267},
publisher = {EDP-Sciences},
volume = {45},
number = {2},
year = {2011},
doi = {10.1051/ita/2011105},
mrnumber = {2811657},
zbl = {1218.68090},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2011105/}
}
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 SP - 249 EP - 267 VL - 45 IS - 2 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita/2011105/ DO - 10.1051/ita/2011105 LA - en ID - ITA_2011__45_2_249_0 ER -
%0 Journal Article %A Komm, Dennis %A Královič, Richard %T Advice Complexity and Barely Random Algorithms %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2011 %P 249-267 %V 45 %N 2 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita/2011105/ %R 10.1051/ita/2011105 %G en %F ITA_2011__45_2_249_0
Komm, Dennis; Královič, Richard. Advice Complexity and Barely Random Algorithms. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011) no. 2, pp. 249-267. doi: 10.1051/ita/2011105
Cité par Sources :