Synchronized Hypermedia Documents and Tension Problems in a Graph

Everybody knows now HTML, which is the most popular language to publish documents on the Internet. It brings new facilities compared to the classic paper material, mainly because of its interactivity capabilities and its integration of multimedia. But as always, needs grow and new languages are developed to improve the structure and the interactivity of documents. Notably languages as SMIL (Synchronized Multimedia Integration Language) appeared. They bring new dynamics in hypermedia documents, and particularly the possibility of animating and synchronizing media components in them.

The variety of components that form a document (audio, video, text, image...) makes the animation a difficult problem. The author of a synchronized document provides a set of constraints in a way that describes the progress of the presentation. Each of these components has a duration of presentation that is flexible within some boundaries. The problem consists in finding a good adjustment of the durations so the presentation progresses as close as possible to what the author wants with avoiding any pause in the presentation. This problem can be modeled, with some restrictions, as a minimum cost tension problem in a graph.

To solve this problem, we propose an adaptation of the out-of-kilter algorithm in the case of piecewise linear costs and in the case of non linear convex costs. We also propose a Lagrangian relaxation of the tension problem with integer values in the case of piecewise linear costs. It can be considered as a minimum cost flow problem that is solved with an adaptation of the cost-scaling algorithm. This second method is proposed in a recent work of R.K. Ahuja, D. Hochbaum and J.B. Orlin. Numerical tests show the interest of this modeling for the optimization of the quality of presentation of hypermedia documents. We end with the presentation of a very peculiar class of constraints, modeled by series-parallel graphs, that represent an idealization of the problem.