Optimization of the Presentation of a Hypermedia Document

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 the language SMIL (Synchronized Multimedia Integration Language), based on XML (next standard for the publication of documents on the Internet), appeared. It brings 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 (moments when nothing happens). This adjustment must be scheduled before the presentation of the document, but it may be modified later during the presentation, because of interactions with the user or possible delays related to transfers in the network.

We collaborate with a Brazilian research team that develops tools to design and present such documents. We contribute to this work by providing fast algorithms that answer some of the different problems presented above. We explain here how to model these problems with graphs and which possibilities we have to estimate the quality of a presentation. We focus then more specifically on one of these problems, which can be modeled as a minimum cost tension problem in a graph. To solve it, 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. 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.