Online algorithms with Advice

Context

Online computation with advice has been introduced in previous work involving members of this project.

It is a new, general framework whose purpose is to model online algorithms which have access to some

limited information about the future. The purpose of the advice model is to analyze the impact of such

information on the attained competitive ratio. One important feature of our famework is that it takes a

quantitative and general approach for measuring the amount of available information about the future and

its impact on the performance of the online algorithm. This is as opposed to the few ad-hoc and specific-to-the-problem

attempts previously made to deal with partial information about the future (for example, lookahead, i.e., the knowledge

of a certain window of future input items).

Since an online algorithm typically has at any time a finite set of possible actions, the advice setting provides a

smooth spectrum of computation models. More precisely, it lies in between two extremes, namely, on the one

hand, (standard) online computation with no advice, and on the other hand, offline computation, where the

advice is simply the optimal action that should be performed in a state of full information.

Objectives

In this project we address fundamental online problems from the perspective of the design of online algorithms

that have partial information about the future. More precisely, we are interested in the interplay between

the amount of information about the future such online algorithm has, and the achievable competitive ratio.

The two central parameters in this framework are the number of bits of advice received with each request,

and the achievable competitive ratio for the problem. Our aim is to establish upper and lower bounds on the

achievable competitive ratio as a function of the number of bits of advice per request (and possibly other

parameters of the problem). Our eventual goal, at least for some of the problems we study, is to achieve

tight upper and lower bounds, i.e., to establish tradeoffs between the amount of information about the future

available to the algorithm and the achievable competitive ratio.

Results

Coming soon!