On-line algorithms for expert advice and task systems

Carl Burch

Thesis, May 20, 2000

Thesis proposal, February 16, 1999


This thesis explores two general on-line scenarios historically deriving from two largely disjoint communities. Though the problems are inherently similar, the techniques and questions developed for these two problems are very different; an examination of them provides new insights and new directions, each enriching the other. From machine learning comes the problem of predicting from expert advice - that is, of choosing one of several experts for each query in a sequence without doing much worse than the best expert overall. And from competitive analysis comes metrical task systems, where the algorithm is to decide in which state to process each of several sequential tasks, where each task specifies the processing cost in each state, but changing states also has a cost according to a metric.

Besides connecting these problems, the thesis presents a variety of results lying in and around the area defined by them, including interesting hybrid problems (adding a switching cost between experts) or generalizations (a task system where the algorithm occupies several states). This thesis answers a long-standing question in competitive analysis by proving the first polylogarithmic competitive ratio for task systems in general metric spaces.


Avrim Blum (chair)
Allan Borodin
Bruce Maggs
Danny Sleator

On-line algorithms for expert advice and task systems / Publications / Carl Burch / 12 Feb 1999