The Moser-Tardos Resample algorithm: Where is the limit? (an experimental inquiry)
Jan Dean Catarata, Scott Corbett, Harry Stern, Márió Szegedy, Tomáš Vyskočil, Zheng Zhang · 2017
The celebrated Lovász Local Lemma (LLL) guarantees that locally sparse systems always have solutions. The Moser-Tardos Resample algorithm does not only find such a solution in linear time, but its beautiful analysis has greatly enhanced LLL related research [9, 10]. Nevertheless two major questions remain open. How far beyond Lovász's condition can we expect that Resample still performs in polynomial (linear) expected running time? In Resample we have a choice between different constraint-selection strategies. How much does this choice matter? To state the first question correctly is a challenge already. For a solvable fixed instance Resample always comes up with a solution, but the catch is that the number of steps may be very large. We have therefore looked at parameterized instance families and tried to identify phase transitions in terms of these parameters. Perhaps the biggest lesson we have learned is that if we want to see phase transition thresholds, i.e. identify parameter values where Resample “stops working,” we need to understand what happens when Resample does not work. We have noticed that in this case the algorithm settles at a metastable equilibrium (at least for the homogenous instances we have considered), a phenomenon mostly studied for physical systems. Concerning the policies for picking the violated constraints (such as first violated, random violated, recursive fix, etc.), in the context of the grid-coloring problem the methods worked exactly for the same parameter range the number of resample steps differed by no more than 20 percent. All results are experimental, although we discuss a possible reason behind some phenomena.