Open access
Date
2010Type
- Report
ETH Bibliography
yes
Altmetrics
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 apply 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. Show more
Permanent link
https://doi.org/10.3929/ethz-a-006875015Publication status
publishedJournal / series
Technical reportVolume
Publisher
ETH, Department of Computer ScienceOrganisational unit
02150 - Dep. Informatik / Dep. of Computer Science
Notes
Technical Reports D-INFK.More
Show all metadata
ETH Bibliography
yes
Altmetrics