Speaker: Joan Boyar, University of Southern Denmark
Title: Complexity classes for online algorithms via advice complexity
In studying online algorithms with advice, one attempts to measure how much knowledge of the future is necessary and sufficient to achieve a given competitive ratio. The lower bound results give robust bounds on what is possible using semi-online algorithms. On the other hand, when the advice is realistically obtainable, algorithms with advice can lead to semi-online algorithms.
The study of advice complexity has led to the first complexity classes for online algorithms. The first class, Asymmetric Online Covering (AOC), contains many problems where the algorithm’s irrevocable decisions are whether to accept or reject requests. All AOC-complete problems, such as VERTEX COVER, INDEPENDENT SET, DOMINATING SET, CYCLE FINDING, and DISJOINT PATH ALLOCATION, have essentially the same advice complexity (linear in n/c, where n is the number of requests and c is the desired competitive ratio). Weighted versions of the known AOC-complete minimization problems are even harder. These complexity classes are not only interesting with respect to advice; in the online setting without advice, the complete problems are also exceptionally hard.
This is joint work with Lene Monrad Favrholdt, Christian Kudahl, and Jesper With Mikkelsen.