| Meno: | Michal
|
|---|
| Priezvisko: | Petrucha
|
|---|
| Názov: | Selected Topics from Advice Complexity
|
|---|
| Vedúci: | RNDr. Michal Forišek, PhD.
|
|---|
| Rok: | 2014
|
|---|
| Blok: | INF
|
|---|
| 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.
|
|---|