Hypermedia Synchronization: Modeling and Optimization with Graphs

The exploding use of Internet and of hypermedia documents has turned crucial the necessity to dispose of robust online algorithms to manage complexity and interactivity. One of the resulting problems which has emerged recently is the synchronization of hypermedia documents by considering that each media object can be compressed or delayed like an elastic spring. The heterogeneity of the objects that compose a hypermedia document turns their presentation in time and space a hard problem. On the other hand, interactivity imposes that real-time updates of the schedule of the document should be possible, increasing the need for faster decision-making algorithms.

Hypermedia documents are composed of media objects (audio, video, text, image...), which duration of presentation must be adjusted to satisfy a set of temporal constraints that express the progress of the animation as defined by the author. But for these constraints to be satisfied, the author must accept some flexibility on the duration (that we call "ideal") of presentation of each object, pauses being totally forbidden if not explicitly wanted. To estimate the quality of an adjustment, a cost function, usually convex, is introduced for each object. To sum up, the problem we attempt to solve here is to find an adjustment of best quality, i.e. which minimizes the sum of the costs of the media objects. It is identified as the "minimum cost tension" problem in a graph. We study three different models, depending on the kind of costs (piecewise linear or boolean functions) and durations flexibility (continuous intervals or sets of discrete values).

In the first model, costs are convex piecewise linear functions and duration flexibility is expressed with continuous intervals. The problem can be modeled with continuous linear programs. It is a solution widely used in practice for the synchronization problem. Another way to solve the problem is the "out-of-kilter" algorithm first introduced for the "minimum linear cost flow" problem. We propose an adaptation of that method to piecewise linear costs. That algorithm is pseudo-polynomial. More recently, an algorithm was proposed to solve a more generic problem called the "convex cost integer dual network flow" problem. It consists in transforming the minimum cost tension problem into a minimum cost flow problem, solved with the well-known "cost-scaling" method. This algorithm is polynomial. We discuss a practical comparison of these methods and how they can be used in hypermedia synchronization software.

Authors of hypermedia documents often need to minimize the number of media objects that are not scheduled at their ideal value, the duration flexibility still being expressed by continuous intervals. However, due to the boolean nature of the cost functions, the techniques previously described can not be used directly anymore, since the problem now belongs to the family of mixed integer programming. We propose a method based on linear relaxation to solve the problem. We show that it is still possible to use the tension formulation within the relaxation, which allows us to define efficient strategies based on methods presented for the first model to get very good solutions in a reasonable amount of time.

In the last variation of the problem, we consider a set of discrete values to express the duration flexibility of each media object, instead of continuous intervals. The cost is still supposed to be a piecewise linear function. We propose an integer formulation that involves binary/decision variables for each possible value of each flexibility set. This kind of problem has been shown to be much harder to solve within the context of linear programming. Preliminary results are presented.