Méthode d'agrégation pour les problèmes de tension

L'étude de problèmes de tension dans les graphes est motivée ici par des problèmes de synchronisation dans les documents hypermédia (cf. [2]). Ces derniers sont composés de divers objets multimédia tels que du son, de la vidéo, du texte, une image, une applet... Les auteurs ont besoin d'outils puissants pour planifier automatiquement les spécifications temporelles de ces objets dans un document. Chaque objet multimédia u possède une durée intrinsèque, dite également idéale, o_u et un intervalle [a_u;b_u] dans lequel sa durée effective (i.e. planifiée) peut varier. L'auteur spécifie également des contraintes temporelles dans le but de décrire le déroulement de la présentation du document. Le problème se résume finalement à planifier une durée pour chaque objet multimédia afin de satisfaire à la fois les intervalles de tolérance et les contraintes temporelles.

Ce problème peut être interprété comme un problème de tension de coût minimum dans un graphe. Soit une fonction qui affecte un potentiel à chaque noeud d'un graphe G = (X;U). La tension d'un arc u = (x;y) est la différence de potentiels et est contrainte à . Le problème de la tension de coût minimum peut se modéliser par:

Pour mesurer la qualité d'un document, plusieurs propositions ont été faites. Les premières études ont considéré des coûts linéaires par morceau, avec un minimum en o_u (e.g. [4]). Le problème peut alors être exprimé comme un programme linéaire et plusieurs algorithmes polynômiaux ont été développés (e.g. [1]). Récemment, nous avons proposé une méthode d'agrégation (cf. [3]) qui résout le problème de la tension minimum à coûts convexes linéaires par morceaux (ou problème CPLCT) sur des graphes série-parallèles (ou SP-graphes). Cette approche s'est révélée compétitive avec les meilleurs algorithmes sur cette classe de graphes.

Cependant, le nombre d'objets qui doivent être modifiés (i.e. qui ne sont pas planifiés à leur durée idéale) est également très pertinent pour la synchronisation hypermédia. En effet, altérer la durée d'un objet multimédia est très coûteux en temps de calcul, et on comprend donc, dans un contexte temps réel, l'importance de minimiser cette opération (cf. [5]). Nous proposons ici une approche par agrégation pour le problème de la tension minimum à coûts binaires (ou problème BCT) dans un SP-graphe, où les fonctions de coût sont définies par:

De part sa nature discrète, ce problème est NP-complet, aussi bien pour des graphes quelconques que pour des graphes série-parallèles (cf. [5]).

Notre intérêt pour les SP-graphes s'explique par la structure très proche du série-parallèle des contraintes temporelles utilisées pour l'hypermedia. Malgré tout, les SP-graphes traduisent des situations trop idéales. La notion de quasi-k SP-graphes est donc introduite pour regrouper les graphes dont la propriété série-parallèle est quelque peu altérée (ajout d'arcs perturbateurs). Ces graphes traduisent alors parfaitement les besoins d'expression de synchronisation entre objets multimédia.

En résumé, nous introduisons les SP-graphes et la méthode générale d'agrégation, et présentons brièvement son application au problème CPLCT pour des SP-graphes, avant de l'étendre et de la combiner avec la mise à conformité (out-of-kilter) pour résoudre le problème sur des quasi-k SP-graphes. Pour cette dernière approche, appelée reconstruction, le problème de la décomposition d'un graphe quelconque en composantes série-parallèles est abordé. Nous proposons également une application de la méthode d'agrégation au problème BCT. Enfin, nous concluons par une étude comparative, à la fois théorique et pratique, de ces méthodes avec celles existantes.