Search
Results
-
Stabilization Time in Weighted Minority Processes
(2019)Leibniz International Proceedings in Informatics (LIPIcs) ~ 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)A minority process in a weighted graph is a dynamically changing coloring. Each node repeatedly changes its color in order to minimize the sum of weighted conflicts with its neighbors. We study the number of steps until such a process stabilizes. Our main contribution is an exponential lower bound on stabilization time. We first present a construction showing this bound in the adversarial sequential model, and then we show how to extend ...Conference Paper