
Open access
Date
2015-11-25Type
- Report
ETH Bibliography
yes
Altmetrics
Abstract
In the model of advice complexity for online problems, an online algorithm is amended by an advice tape prepared by an oracle that knows the whole input in advance, and it is measured how many bits from this tape an online algorithm has to read in order to reach a certain solution quality. This model was introduced and successfully applied as a means for an improved analysis of the hardness of online problems. It was shown that it has strong connections to randomized computations, e. g., lower bounds on the advice complexity can be used to prove lower bounds also on randomized algorithms. In this paper, we complement these known results with a method for constructing randomized online algorithms from online algorithms with advice. More precisely, we consider task systems, which model many well-known online problems such as paging, k-server, ski rental, etc. For these problems, we show how to transform any online algorithm using a small amount of advice into a randomized algorithm with almost the same competitive ratio. We achieve this by using methods from algorithmic learning theory. Using this result, we furthermore show how to translate lower bounds on randomized online computations into lower bounds for the advice complexity. Show more
Permanent link
https://doi.org/10.3929/ethz-a-010556417Publication status
publishedPublisher
ETH ZürichSubject
SPECIAL PROGRAMMING METHODS; PROGRAMS AND ALGORITHMS FOR THE SOLUTION OF SPECIAL PROBLEMS; SPEZIELLE PROGRAMMIERMETHODEN; PROBLEMLÖSEN + PLANEN + SUCHEN (KÜNSTLICHE INTELLIGENZ); PROBLEM SOLVING + PLAN GENERATION + SEARCH (ARTIFICIAL INTELLIGENCE); PROGRAMME UND ALGORITHMEN ZUR LÖSUNG SPEZIELLER PROBLEMEOrganisational unit
03666 - Hromkovic, Juraj (emeritus) / Hromkovic, Juraj (emeritus)
02150 - Dep. Informatik / Dep. of Computer Science
More
Show all metadata
ETH Bibliography
yes
Altmetrics