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!