# Advice Complexity and Barely Random Algorithms

RAIRO - Theoretical Informatics and Applications (2011)

- Volume: 45, Issue: 2, page 249-267
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topKomm, Dennis, and Královič, Richard. "Advice Complexity and Barely Random Algorithms." RAIRO - Theoretical Informatics and Applications 45.2 (2011): 249-267. <http://eudml.org/doc/222011>.

@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},

keywords = {Barely random algorithms; advice complexity; information content; online problems; barely random algorithms},

language = {eng},

month = {6},

number = {2},

pages = {249-267},

publisher = {EDP Sciences},

title = {Advice Complexity and Barely Random Algorithms},

url = {http://eudml.org/doc/222011},

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

DA - 2011/6//

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; barely random algorithms

UR - http://eudml.org/doc/222011

ER -

## References

top- D. Achlioptas, M. Chrobak and J. Noga, Competitive analysis of randomized paging algorithms. Theoret. Comput. Sci.234 (2000) 203–218.
- 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.
- H.-J. Böckenhauer, D. Komm, R. Královič, R. Královič and T. Mömke, Online algorithms with advice. To appear.
- A. Borodin and R. El-Yaniv, Online computation and competitive analysis. Cambridge University Press, New York (1998).
- P. Brucker, An efficient algorithm for the job-shop problem with two jobs. Computing40 (1988) 353–359.
- 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.
- Y. Emek, P. Fraigniaud, A. Korman and A. Rosén, Online computation with advice. Theoret. Comput. Sci.412 (2010) 2642–2656.
- J. Hromkovič, Design and analysis of randomized algorithms: Introduction to design paradigms. Springer-Verlag, New York (2006).
- 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.
- J. Hromkovič, T. Mömke, K. Steinhöfel and P. Widmayer, Job shop scheduling with unit length tasks: bounds and algorithms. Algorithmic Operations Research2 (2007) 1–14.
- 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.
- 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.
- N. Reingold, J. Westbrook and D. Sleator, Randomized competitive algorithms for the list update problem. Algorithmica11 (1994) 15–32.

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.