Advice Complexity and Barely Random Algorithms
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011) no. 2, pp. 249-267.

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.

DOI : https://doi.org/10.1051/ita/2011105
Classification : 68Q25,  68Q30,  68Q87
Mots clés : barely random algorithms, advice complexity, information content, online problems
@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},
     zbl = {1218.68090},
     mrnumber = {2811657},
     language = {en},
     url = {http://www.numdam.org/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
DA  - 2011///
SP  - 249
EP  - 267
VL  - 45
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2011105/
UR  - https://zbmath.org/?q=an%3A1218.68090
UR  - https://www.ams.org/mathscinet-getitem?mr=2811657
UR  - https://doi.org/10.1051/ita/2011105
DO  - 10.1051/ita/2011105
LA  - en
ID  - ITA_2011__45_2_249_0
ER  - 
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. http://www.numdam.org/articles/10.1051/ita/2011105/

[1] D. Achlioptas, M. Chrobak and J. Noga, Competitive analysis of randomized paging algorithms. Theoret. Comput. Sci. 234 (2000) 203-218. | MR 1745075 | Zbl 0944.68194

[2] H.-J. Böckenhauer, D. Komm, R. Královič, R. Královič and T. Mömke, On the advice complexity of online problems, in 20th International Symposium on Algorithms and Computation (ISAAC 2009) Lect. Notes Comput. Sci. 5878 (2009) 331-340. | Zbl 1272.68466

[3] H.-J. Böckenhauer, D. Komm, R. Královič, R. Královič and T. Mömke, Online algorithms with advice. To appear.

[4] A. Borodin and R. El-Yaniv, Online computation and competitive analysis. Cambridge University Press, New York (1998). | MR 1617778 | Zbl 0931.68015

[5] P. Brucker, An efficient algorithm for the job-shop problem with two jobs. Computing 40 (1988) 353-359. | MR 969653 | Zbl 0654.90036

[6] S. Dobrev, R. Královič and D. Pardubská, How much information about the future is needed?, in 34th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM) (2008) 247-258. | Zbl 1132.68422

[7] Y. Emek, P. Fraigniaud, A. Korman and A. Rosén, Online computation with advice. Theoret. Comput. Sci. 412 (2010) 2642-2656. | MR 2828340 | Zbl 1218.68200

[8] J. Hromkovič, Design and analysis of randomized algorithms: Introduction to design paradigms. Springer-Verlag, New York (2006). | MR 2156292 | Zbl 1083.68146

[9] J. Hromkovič, R. Královič and R. Královič, Information complexity of online problems, in 35th International Symposium on Mathematical Foundations of Computer Science (MFCS 2010). Lect. Notes Comput. Sci. 6281 (2010) 24-36. | MR 2727212 | Zbl 1287.68083

[10] J. Hromkovič, T. Mömke, K. Steinhöfel and P. Widmayer, Job shop scheduling with unit length tasks: bounds and algorithms. Algorithmic Operations Research 2 (2007) 1-14. | Zbl 1186.90051

[11] D. Komm and R. Královič, Advice complexity and barely random algorithms, in 37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2011). Lect. Notes Comput. Sci. 6543 (2011) 332-343. | MR 2804133 | Zbl 1298.68116

[12] T. Mömke, On the power of randomization for job shop scheduling with k-units length tasks. RAIRO-Theor. Inf. Appl. 43 (2009) 189-207. | Numdam | MR 2512254 | Zbl 1166.68041

[13] N. Reingold, J. Westbrook and D. Sleator, Randomized competitive algorithms for the list update problem. Algorithmica 11 (1994) 15-32. | MR 1247986 | Zbl 0782.68062

Cité par Sources :