Towards an analysis of local optimization algorithms
Tassos D. Dimitriou, Russell Impagliazzo · 1996
We introduce a variant of Aldous and Vazirani's "Go with the winners" algorithm that can be used for search graphs that are not trees.We analyze the algorithm in terms of the properties of a tree-decomposition of the search graph.We show a large clazs of distributions for search graphs so that "Go with the winners" works well with high probability y for almost all graphs from the distribution.We also give a sufficient combinatorial property that ensures good performance.