This algorithm is a conservative, genetic algorithm-like heuristic, that maintains a collection of solutions uniformly distributed among those that meet a given quality criterion. Carson and Impagliazzo showed how to use this algorithm as a sampler to do experimental, statistical studies of the structure of search graphs. This work led to a clearer picture of how and why various heuristics succeed and fail on some instances of the graph bisection problem. A related theoretical challenge is to find examples of instances that distinguish between various heuristics, where one method provably performs better than others. Carson and Impagliazzo prove that the leading candidate for such problems, a certain distribution of graph bisections, does not distinguish, because almost all heuristic methods solve the problem.
Much work remains.
We want to find provable distinctions between methods. We want a theoretical understanding of when widely used heuristics like simulated annealing succeed.