Videos

Global Optima from Local Algorithms

May 22, 2015
Keywords:
  • Graph algorithms
MSC:
  • 05C85
Abstract
At the heart of every local search procedure is a directed graph on candidate solutions (states) such that every unsatisfying state has at least one outgoing arc. In randomized local search the hope is that a random walk on the graph reaches a satisfying state (sink) quickly. We give a general algorithmic local lemma by establishing a sufficient condition for this to be true. Our work is inspired by Moser's entropic method proof of the Lov'{a}sz Local Lemma (LLL) for satisfiability but completely bypasses the Probabilistic Method formulation of the LLL. Similarly to Moser's argument, the key point is that algorithmic progress is measured in terms of entropy rather than in terms of energy (number of violated constraints) so that termination can be established even under the proliferation of local optima.