Rights / licenseIn Copyright - Non-Commercial Use Permitted
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
SubjectSPECIAL 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 PROBLEME
Organisational unit03666 - Hromkovic, Juraj
02150 - Departement Informatik / Department of Computer Science
NotesWeiterer Autor: Walter Unger.
MoreShow all metadata