Internships

This project funded the following internships on online alorithms

1. Greg Koumoutsos (stage M2, now PhD. student at TU Eindhoven)

Title: Online Algorithms with Advice for the Binary Search Tree Problem

Supervisor: Adi Rosen (LIAFA)

Abstract

We study the binary search tree (BST) problem under the framework of online computation with advice.

The BST problem is defined by a binary search tree and a sequence of requests for access operations on

the nodes of the tree. The objective is to minimize the time of the execution. Despite its importance and

simplicity, this problem is still unsolved and there are a lot of open questions related to it. The problem is

not well understood even in the offline case, as there is not known any efficient optimal (or approximation)

algorithm. For the online case, the most important algorithm is splaying (producing the so-called splay trees)

which is very simple in description and achieves very good performance. Splaying is conjectured to achieve a

constant competitive ratio. This conjecture remains open up to date.

In this Master's thesis we give:

- A detailed description of the models used in the literature and a clear explanation of the relation between them,

which implies that one model widely used lacks of equivalence with the others in general case.

- An 1-competitive algorithm for the binary search tree problem O(\log n) bits of advice per request.

- An extension of the previous algorithm which yields to a logn\alpha-competitive algorithm, logn/loglog n < alpha < log n,

using alpha bits of advice per request.

To the best of our knowledge this is the first research work for BST problem in the setting of advice. Also this

is the first work trying to attack this problem from the point of view of minimizing the number of rotations (primitive

operation for reorganizing the tree). We believe that this direction would contribute to the better understanding of this

operation and its impact on the performance of binary search trees.

2. Maud Doumergue (stage M1, student at Ecole Polytechnique)

Title: Online route planning

Supervisors: Spyros Angelopoulos and Christoph Dürr

Abstarct

The pure dynamic Dial-A-Ride Problem (DARP) consists of scheduling vehicles’ routes under real-time demand

from customers, who ask for transport between pickup and delivery localisations. The rides can be shared.

The aim is not only to serve as many requests as possible, but also to offer a quality service as human beings

and not parcels are being considered. With a quite diffuse litterature on the subject, different models have

been studied and no standardized benchmarck exists.

Turning towards online computation, we have tried to find connexions with the k-server problem. We have

also seeked ideas from stochastic algorithms to handle the possibility of a probabilitic demand. In the end,

a realistic model for the pure dynamic DARP is presented, as well as a simulation environment based on

Vélib data in Paris, on which an algorithm has been tested.