Couverture de sommets “on-line”

En algorithmique “on-line”, l’instance d’un problème est révélée petit à petit et l’on doit prendre, pour la construction de la solution, des décisions irrévocables sur la base d’informations encore incomplètes. Cette situation peut être représentée par un jeu à deux joueurs dans lequel le premier joueur (appelé souvent l’adversaire) révèle l’instance que le second tente de résoudre. Le but est d’étudier la qualité de la solution que peut se garantir le second joueur, qualité exprimée par un rapport de compétitivité (rapport entre la valeur garantie et la valeur que pourrait se garantir un joueur connaissant a priori l’instance).

Dans cet exposé, nous nous intéresserons au cas de la couverture de sommets envisagé sous différents modèles “on-line” qui correspondent à différentes règles à respecter pour révéler le graphe. Nous considèrerons d’abord le cas où le graphe est révélé sommet par sommet : à chaque étape un nouveau sommet est révélé ainsi que ses connexions aux sommets connus et le second joueur doit immédiatement décider si ce sommet doit être ou non inclus dans la solution. Dans d’autres modèles au contraire le graphe est révélé par paquets (sous-graphes induits de l’instance). Enfin un modèle tout à fait différent est le cas d’un graphe révélé arête par arête.

Pour chaque cas nous proposons des stratégies du second joueur et leur analyse de compétitivité permettant d’établir des bornes supérieures pour le rapport de compétitivité. Ces résultats sont à confronter à des bornes inférieures que nous obtenons en étudiant des stratégies de l’adversaire pour révéler l’instance.

Enfin, nous envisageons la possibilité, pour le second joueur, de revenir sur certaines décisions moyennant un coût. Pour deux modèles de coûts – linéaire et quadratique – nous étudions comment évoluent les possibilités de garanties.