Dynamique de la diffusion de l'erreur sur plusieurs polytopes (English title: Dynamics of Error Diffusion on Several Polytopes)

We discuss greedy algorithms for scheduling and in particular for digital printing, with inputs in a family of polytopes lying in an affine space and vertices of the respective polytopes as successive outputs. More precisely we consider here the case when the greed of the algorithm is dictated by the Euclidean norms of the successive cumulative errors. Scheduling problems with many polytopes arise naturally, for instance when one has a priori a single polytope P but with the constraint that the output has to be in the same face as the input whenever the input belongs to a face. We provide some simple examples where the error remains bounded, including cases when there are infinitely many polytopes. In the case of a single polytope the boundedness of the cumulative error is known to be equivalent to the existence of an invariant region for a dynamical system in the a±ne space that contains that polytope, a dynamical system which is just a rewriting of the original dynamics that lives in the vector space that contains the successive cumulative errors. We show here that to the contrary, no bounded invariant region can be found in affine space in general, as soon as there are at least two different polytopes.