Dynamique de la diffusion de l'erreur sur plusieurs polytopes - 01/01/04
Charles Tresser 1
Voir les affiliationspages | 6 |
Iconographies | 0 |
Vidéos | 0 |
Autres | 0 |
Résumé |
Nous discutons des algorithmes gloutons (pour la norme euclidienne), avec des suites de données dans une famille de polytopes d'un espace affine et les résultats pris parmis les sommets des polytopes respectifs. De tels problèmes d'ordonnancement interviennent dans divers domaines d'applications. Nous produisons quelques exemples simples où l'erreur demeure bornée, même avec une infinité de polytopes. Dans le cas d'un seul polytope, il a été montré par ailleurs, que le caractère borné de l'erreur cumulée est équivalent à l'existence d'une région invariante pour un système dynamique équivalent à l'algorithme et défini dans l'espace affine qui contient ce polytope. Nous montrons, au contraire, qu'il n'existe pas, en général, de région bornée dès que l'on considère au moins deux polytopes différents. Pour citer cet article : C. Tresser, C. R. Acad. Sci. Paris, Ser. I 338 (2004).
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).
Plan
Vol 338 - N° 10
P. 793-798 - mai 2004 Retour au numéroBienvenue sur EM-consulte, la référence des professionnels de santé.
L’accès au texte intégral de cet article nécessite un abonnement.
Bienvenue sur EM-consulte, la référence des professionnels de santé.
L’achat d’article à l’unité est indisponible à l’heure actuelle.
Déjà abonné à cette revue ?