Accueil des participants

Introduction aux algorithmes de streaming

Frédéric Magniez

CNRS, Université Paris Diderot

Transparents de la présentation

Nous présenterons certains des principaux algorithmes de streaming pour des domaines variées tels que les statistiques, les séquences et les graphes. L'exposé ne supposera aucune connaissance a priori du sujet.

An overview of online computation

Spyros Angelopoulos

LIP6, Université Pierre et Marie Curie

Transparents de la présentation

In online computing we are interested in algorithms that can perform well even when the input is not known in advance, but is instead revealed in pieces over time. The central question one must address is how to get around this absence of information, and how to evaluate the performance of the obtained algorithms. In this presentation I will give an overview of some recent (and older) results that have shaped online computation into a well-established field of theoretical computer science.

Pause déjeuner

A Memory-Efficient Algorithm for Vertex Covering on Huge Graphs

Romain Campigotto

LIP6, Université Pierre et Marie Curie

Transparents de la présentation

Dans cet exposé, nous présentons une heuristique simple pour résoudre le problème du Vertex Cover sur de grands graphes, et nous montrons son efficacité "pratique". Pour cela, après avoir défini un modèle de traitement regroupant certaines propriétés de plusieurs modèles existants dans la littérature (streaming, online, I/O-efficient), nous présenterons notre heuristique, que l'on peut qualifier d'algorithme memory-efficient (car il utilise un espace mémoire en O(log n) bits). Nous donnerons quelques outils d'analyse (qualité et complexité) et de comparaison (indiquant par exemple la taille moyenne des solutions construites sur un graphe donné) ainsi qu'une synthèse de résultats d'expérimentations menées sur de très gros graphes (ayant des tailles > 10 milliards de sommets et d'arêtes). Nous terminerons en proposant une borne inférieure originale sur le nombre indépendant d'un graphe, calculée à partir des outils d'analyse de notre algorithme.

Lagrangian duality in online scheduling

Nguyen Kim Thang

IBISC, Université Evry val d'essonne

Transparents de la présentation

Currently the most successful techniques to design and analyze online algorithms are the potential function and the charging scheme methods, which are all based on the amortized analysis. However, the techniques have their limits and generally one figures out a potential function or a charging scheme by trial and error. A principled approach is essential for improvement in the domain.

The recent primal-dual framework for online algorithms introduced by Buchbinder and Naor was a breakthrough, which has settled many open questions and new directions. However, that framework is not powerful enough against problems in scheduling.

In this talk, we will present a unified approach for online scheduling based on Lagrangian duality. We derive improved algorithms for problems which stand up to current techniques.

Pause café

Online Algorithms with Advice

Marc Renault

LIAFA , Université Paris Diderot

Transparents de la présentation

Online algorithms receive the input in a piecewise manner and must make an irrevocable decision, that engenders a certain cost, on the output before the next piece of the input is revealed. Competitive analysis is the standard method used to analyse the quality of online algorithms wherein the competitive ratio compares the performance of an algorithm with no knowledge of the future against an algorithm with full knowledge of the future. Since the complete absence of future knowledge is often not a reasonable assumption, models termed online algorithms with advice, that give the online algorithms access to a quantified amount of future knowledge, have been proposed. These models are useful for examining how the competitive ratio changes as a function of the amount of advice. In this talk, we will review the two models of online computation with advice and some recent results.