Global Optima from Local Algorithms

Friday, May 22, 2015 - 9:00am - 9:50am
Keller 3-180
Dimitris Achlioptas (University of California)
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.
MSC Code: