Improving Local Search

When solving a problem requires computing time that is exponential in the problem's size, reason dictates a tradeoff: sacrifice a small degree of accuracy for a large gain in speed. For hard discrete optimization problems, this is the motivating principle behind local search heuristics. Effective local search methods exploit the problem's structure in order to provide good near-optimal solutions quickly.

But how good, how near-optimal, and how quickly? A theoretical explanation of the relationship between structure and the success of local search methods has always seemed a distant goal, with progress limited to a few very specific cases. However, some recent developments arising from the efforts of computer scientists, physicists, and mathematicians suggest that the goal is no longer so distant. Results from Markov chain sampling methods as well as from critical phenomena in statistical mechanics make it possible to extract certain clues as to how characteristics of a problem may affect local search performance. We propose to analyze these characteristics, from both a theoretical and a practical point of view. In doing so, our goal is to quantify the performance of local search under a variety of circumstances, and to suggest methods of improved local search.

Publications

• S. Boettcher, G. Istrate and A.G. Percus, ``Spines of random constraint satisfaction problems: definition and impact on computational complexity'' (PDF format), Proceedings of the 8th International Symposium on Artificial Intelligence and Mathematics (AIMATH '04) AI&M 2-2004

• A.G. Percus, G. Istrate and C. Moore, eds., Computational Complexity and Statistical Physics (Oxford University Press, New York, to appear: 2004)

• D. Aldous and A.G. Percus, "Scaling and universality in continuous length combinatorial optimization'' (PDF format or gzip'd Postscript format), Proceedings of the National Academy of Sciences 100, 11211-11215 (2003)

Last modified: 7 March 2004