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 pro blems. To use local search one ''simply'' has to specify a neighborhoo d structure and a cost function which has to be optimized. However, fr om a theoretical point of view, many questions remain unanswered, and one of the most important is: which neighborhood structure will provid e the best quality solutions? The aim of this paper is to theoreticall y justify some results previously reported by Johnson et al. (1989, 19 91) in their extended empirical study concerning simulated annealing a nd the graph bipartitioning problem, and to sharply tune the best land scape among the two reported in that study. Experimental results perfe ctly agree with the theoretical predictions.