Reducing off-line to on-line : an example and its applications

Marc Demange*, ESSEC et CERMSEM

Résumé. Nous étudions des versions on-line de problèmes de sous-graphe induit héréditaire de poids maximum pour lesquelles chaque instance est révélée en deux paquets. Nous nous intéressons à la comparaison de ces problèmes on-line avec leur version off-line. Dans [3], nous proposons, pour de tels problèmes, de réduire le cas on-line au cas off-line ; ceci permet de concevoir des algorithmes compétitifs pour ces problèmes on-line. Dans cet article, nous proposons d'abord des résultats négatifs qui mettent en évidence le caractère optimal de ces analyses. Nous proposons alors une démarche qui permet, pour une large classe de problèmes héréditaires, de transformer un algorithme on -line en un algorithme off-line offrant de meilleures garanties. Ce résultat peut être vu comme une réciproque de notre précédente réduction. Il met en évidence un saut de difficulté entre les versions on-line et off-line de ces problèmes. Il ne s'applique pas au cas de la recherche d'un sous-graphe induit k-colorable maximum (k supérieur ou égal à 2). Pour ce problème, au contraire, nous montrons que la version on-line est aussi bien résolue que la version off-line.
Mots clés : Problèmes combinatoires, algorithmique on-line, réductions, sous-graphe induit héréditaire.

Abstract. We study on-line versions of maximum weighted hereditary subgraph problems for which the instance is revealed in two clusters. We focus on the comparison of these on-line problems with there respective off-line version. In [3], we have reduced on-line versions to off-line ones in order to devise competitivity analysis for such problems. In this paper, we first devise hardness results pointing out that this previous analysis was tight. Then, we propose a process that allows, for a large class of hereditary problems, to transform an on-line algorithm into an off-line on with improvement of the guarantees. This result can be seen as an inverse version of our previous work. It brings to the fore an hardness gap between on-line and off-line versions of those problems. This result does not apply in the case of maximizing a k-colorable induced subgraph (k greater than or equal 2) of a given graph. For this problem we point out that, contrary to the first case, the on-line version is almost as well approximated as the off-line one.
Keywords : Combinatorial problems, on-line computation, reductions, hereditary subgraph problem.

AMS Classification : 03D15, 68Q25, 68R05.

*ESSEC, dépt. SID, Av. B. Hirsch B.P. 105, 95021 Cergy-Pontoise Cedex, France.