Dynamique de la diffusion de l'erreur sur plusieurs polytopes |
| |
Authors: | Charles Tresser |
| |
Institution: | IBM, P.O. Box 218, Yorktown Heights, NY 10598, USA |
| |
Abstract: | We discuss algorithms for scheduling, greedy for the Euclidean norm, with inputs in a family of polytopes lying in an affine space and the corresponding outputs chosen among the vertices of the respective polytopes. Such scheduling problems arise in various settings. We provide 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 affine space that contains this polytope. We show here that, on the contrary, no bounded invariant region can be found in affine space in general, as soon as there are at least two different polytopes. To cite this article: C. Tresser, C. R. Acad. Sci. Paris, Ser. I 338 (2004). |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|