Upper bounds for stabilization in acyclic preference-based systemsReportar como inadecuado

Upper bounds for stabilization in acyclic preference-based systems - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 Orange Labs Issy les Moulineaux 2 GANG - Networks, Graphs and Algorithms LIAFA - Laboratoire d-informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt

Abstract : Preference-based systems p.b.s. describe interactions between nodes of a system that can rank their neighbors. Previous work has shown that p.b.s. converge to a unique locally stable matching if an acyclicity property is verified. In the following we analyze acyclic p.b.s. with respect to the self-stabilization theory. We prove that the round complexity is bounded by n-2 for the adversarial daemon. The step complexity is equivalent to n^2-4 for the round robin daemon, and exponential for the general adversarial daemon.

Keywords : acyclicity adversarial b-matching preference-based systems round robin and adversarial daemons

Autor: Fabien Mathieu -

Fuente: https://hal.archives-ouvertes.fr/


Documentos relacionados