We establish and explore a new connection between two general on-line scenarios deriving from two historically disjoint communities. Though the problems are inherently similar, the techniques and questions developed for these two scenarios are very different. From competitive analysis comes the problem of 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, and the algorithm must pay according to a metric to move between states. And 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.

The dissertation includes four results touching on this connection. We begin with the first metrical task system algorithm that can guarantee for every task sequence that the ratio of its expected cost to the cheapest way to process the sequence is only polylogarithmic in the number of states. Then we see how we can use expert-advice results to combine on-line algorithms on-line if there is a fixed cost for changing between the on-line algorithms. The third result establishes new expert-advice algorithms deriving from metrical task system research; in addition to establishing theoretical bounds, we compare the algorithms empirically on a process migration scenario. Finally, we investigate a modified version of paging, where we want to do well against an adversary who is allowed to ignore a paging request cheaply.

80 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by reports@cs.cmu.edu