Overview

an ANR grant 1/11/2011 - 31/10/2015 (grant page on ANR site)

permanent members:

LIAFA: Pierre Fraigniaud (CNRS), Adi Rosén (CNRS, coordinator),

LIP6: Spyros Angelopoulos (CNRS), Christoph Dürr (CNRS),

other members:

Marc Renault, defended his PhD student at LIAFA, spent one year ATER-postdoc at LIP6 (2014-2015)

Giorgio Lucarelli, one-year postdoc at LIP6 (2013-2014), now postdoc at the University of Grenoble-Alpes

Shahin Kamali, 3-month visitor in 2014 in both sites

Moti Medina, one-year postdoc at LIAFA (2014-2015)

Online computation is an established and very active field in Theoretical Computer Science. It deals with the

design and analysis of algorithms that operate in a setting in which the algorithm receives the input piece by

piece, and has nevertheless to perform a (costly) action upon the receipt of each such piece. The most notable

of these situations is when the input is received over time, and the algorithm does not know the future pieces

of information to be received. Since the introduction of competitive analysis by Sleator and Tarjan in 1985, a

very large number of problems have been analyzed using this framework, and numerous important results

have been obtained.

This widespread and fruitful research activity has nevertheless revealed a number of weaknesses of classical

competitive analysis. On the one hand, competitive analysis usually assumes that the online algorithm has

absolutely no knowledge about the future, whereas there are cases in which some information is available.

On the other hand, competitive analysis compares the performance of the online algorithm to the utopian concept

of a clairvoyant offline algorithm that knows the entire future in advance. The comparison to such a powerful

algorithm often results in an undesired too coarse classification of algorithms, that fails to distinguish between

algorithms whose difference is observed in practice.

In this proposal, we plan to address these issues using new techniques that we introduced recently. More precisely,

we plan to study the interplay between the amount of information concerning the future available to the algorithm,

and the achievable competitive ratio, using our framework of online computation with advice. Moreover, we intend

to study the relative performance of online algorithms using our technique of bijective analysis. Furthermore, we

would like to try to combine these new techniques so as to obtain new insights in the field of online computation.

In addition to obtaining specific new results, our objective in this project is to establish the applicability and usefulness

of the novel techniques we introduced in recent years. We also aim to refine and possibly combine them, and to

demonstrate their usefulness in a wider context. Thus, one of our main objectives is to build a solid foundation for

these techniques to be used in the field in the future.