Two-steps combinatorial optimization

Marc Demange, ESSEC et CERMSEM
Vangelis Th. Paschos, LAMSADE, Université Paris-Dauphine

Résumé. Nous présentons des résultats dans le cadre de l'optimisation combinatoire à deux phases qui correspond, en un certain sens, à la frontière entre l'optimisation combinatoire classique et l'algorithmique on-line. Ce cadre suppose que l'instance est révélée en deux paquets. Lorsqu'une première partie de l'instance a été révélée, on doit prendre des décisions irrévocables concernant la fraction de la solution correspondant à cette partie. A la fin de la seconde étape (toute l'instance est connue), on doit compléter la solution précédente en une solution réalisable de l'instance globale. Au moyen d'analyses de compétitivité, nous comparons la résolution de modèles de ce type avec celle que l'on peut obtenir si l'ensemble de l'instance est connu a priori. Dans cet article, nous étudions certains problèmes héréditaires naturels ainsi que la couverture de sommets et le bin-packing.
Mots clés : Algorithmes on-line, rapport de compétitivité, rapport d'approximation.

Abstract. We present results dealing with two-phases optimization which, in some sense, is the boundary between usual and on-line combinatorial optimization. It supposes that the instance to be solved is revealed in two steps. Once the first step reveals a part of the instance, one has to irrevocably construct the partial solution dealing with this part ; at the end of the second step, she/he has to complete the partial solution in order to fit the whole instance. Using competitive analysis, we compare solutions obtained under this model with the ones obtained when instance is known before starting the solution process. In this paper, we study some natural induced hereditary subgraph problems, as well as vertex-covering and bin-packing.
Keywords : On-line algorithm, Competitivity ratio, approximation ratio.

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