Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-26T17:15:55.281Z Has data issue: false hasContentIssue false
  • English
  • Français

Advice Complexity and Barely Random Algorithms

Published online by Cambridge University Press:  24 June 2011

Dennis Komm  and
Richard Královič
Dennis Komm
Affiliation:
Department of Computer Science, ETH Zurich, Switzerland. [email protected]
Richard Královič
Affiliation:
Department of Computer Science, ETH Zurich, Switzerland. [email protected]
Get access

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.

Keywords

Barely random algorithmsadvice complexityinformation contentonline problems
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 45 , Issue 2 , April 2011 , pp. 249 - 267
Copyright
© EDP Sciences, 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Achlioptas, D., Chrobak, M. and Noga, J., Competitive analysis of randomized paging algorithms. Theoret. Comput. Sci. 234 (2000) 203–218. CrossRef
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).
Brucker, P., An efficient algorithm for the job-shop problem with two jobs. Computing 40 (1988) 353–359. CrossRef
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.
Emek, Y., Fraigniaud, P., Korman, A. and Rosén, A., Online computation with advice. Theoret. Comput. Sci. 412 (2010) 2642–2656. CrossRef
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.
Hromkovič, J., Mömke, T., Steinhöfel, K. and Widmayer, P., Job shop scheduling with unit length tasks: bounds and algorithms. Algorithmic Operations Research 2 (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.
Mömke, T., On the power of randomization for job shop scheduling with $k$-units length tasks. RAIRO-Theor. Inf. Appl. 43 (2009) 189–207. CrossRef
Reingold, N., Westbrook, J. and Sleator, D., Randomized competitive algorithms for the list update problem. Algorithmica 11 (1994) 15–32. CrossRef