Názov:Selected Topics from Advice Complexity
Vedúci:RNDr. Michal Forišek, PhD.
Kľúčové slová:online problem, advice complexity, competitive analysis, disjoint path allocation, subset sum
Abstrakt:This work focuses on computation with advice, a relatively new model for measuring the complexity of online problems. First, we give an overview of common methods of analysis of the advice complexity of online problems. Then, we show new upper and lower bounds on the advice complexity of near-optimal solutions of the disjoint path allocation problem. Finally, we introduce a model of offline computation with advice and lay out a basic framework for future research in this area.

Súbory diplomovej práce: