On-line vertex-covering

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

Résumé. En algorithmique on-line, l'instance d'un problème est révélée pas à pas et l'on doit, à la fin de chaque pas, décider de manière irrévocable la partie correspondante de la solution. Nous commençons par l'étude du problème de couverture de sommets sous deux modèles on-line correspondant à deux manières de révéler les sommets. Le premier implique que le graphe est révélé sommet par sommet. Le second modèle, quant à lui, met en jeu un graphe révélé par paquets, chaque paquet correspondant à un sous-graphe induit du graphe final. Sous le modèle par paquets nous relaxons alors la contrainte d'irrévocabilité des choix en autorisant un "backtracking". Nous supposons que l'on peut revenir sur des décisions moyennant un coût fonction du nombre de modifications. Enfin, nous terminons par l'étude d'un modèle pour lequel l'instance est révélée par arête par arête.
Mots clés : Algorithmes on-line, couverture de sommets, rapport de compétitivité, rapport d'approximation.

Abstract. In on-line computation, the instance of a problem is revealed step-by-step and one has, at the end of each step, to irrevocably decide on the part of the final solution dealing with this stem. We first study the minimum vertex-covering problem under two on-line models corresponding to two different ways vertices are revealed. The former one implies that the input-graph is revealed vertex-by-vertex. The second model implies that the input-graph is revealed per clusters, i.e., per induced subgraphs of the final graph. under the cluster-model, we then relax the constraint that the choice of the part of the final solution dealing with each cluster has to be irrevocable, by allowing backtracking. We assume that one can change decisions upon a vertex membership of the final solution, this change implying, however, some cost depending on the number of the vertices changed. Finally we study simple model where instance is revealed edge-by-edge.
Keywords : On-line algorithm, vertex-covering, competitivity ratio, approximation ratio.

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