Documents hypermédia synchronisés et problèmes de tension dans un graphe

Tout le monde connaît maintenant le HTML qui est le langage favori pour la diffusion de documents sur Internet. Il apporte de nouvelles possibilités par rapport au support papier grâce à ses capacités d'interactivité et à son intégration du multimédia. Mais comme toujours, les besoins augmentent et de nouveaux langages sont développés pour améliorer la structure et l'interactivité des documents. Notamment des langages comme SMIL (Synchronized Multimedia Integration Language) ont fait leur apparition. Ils offrent une nouvelle dynamique aux documents hypermédia, et en particulier la possibilité d'y animer et synchroniser des composants multimédia.

La variété des composants qui forment un document (audio, vidéo, texte, image...) fait de l'animation un problème compliqué. L'auteur d'un document synchronisé fournit une liste de contraintes temporelles sur les composants de manière à décrire le déroulement de la présentation. Ces composants ont chacun une durée de présentation qui est flexible dans une certaine limite. Tout le problème consiste à trouver un bon ajustement des durées pour que la présentation se déroule au plus proche de ce que souhaite l'auteur tout en évitant les pauses. Ce problème peut se modéliser, après quelques restrictions, comme un problème de tension de coût minimum dans un graphe.

Pour le résoudre, nous proposons une adaptation de l'algorithme de mise à conformité (out-of-kilter) dans le cas de coûts linéaires par morceaux et dans le cas de coûts non linéaires convexes. Nous proposons également une relaxation Lagrangienne du problème de tension en valeurs entières dans le cas de coûts linéaires par morceaux. Elle peut être considérée comme un problème de flot de coût minimum que l'on résout par une adaptation de l'algorithme de mise à l'échelle (cost-scaling). Cette seconde méthode est proposée dans un travail récent de R.K. Ahuja, D. Hochbaum et J.B. Orlin. Des tests numériques montrent l'intérêt de cette modélisation pour l'optimisation de la qualité de présentation de documents hypermédia. Enfin, nous terminerons avec la présentation d'une classe de contraintes très particulières, modélisées par des graphes série-parallèles, qui représentent une idéalisation du problème.