Autocorrelation coefficient for the graph bipartitioning problem

Local search and its variants simulated annealing and tabu search are widely used heuristics to approximately solve NP-hard optimization problems. To use local search one "simply" has to specify a neighborhood structure and a cost function which has to be optimized. However, from a theoretical point of view, many questions remain unanswered, and one of the most important is: which neighborhood structure will provide the best quality solutions? The aim of this paper is to theoretically justify some results previously reported by Johnson et al. (1989, 1991) in their extended empirical study concerning simulated annealing and the graph bipartitioning problem, and to sharply tune the best landscape among the two reported in that study. Experimental results perfectly agree with the theoretical predictions.