On the quality of local search for the quadratic assignment problem

Local search is widely used to solve approximately NP-complete combinatorial optimization problems. But, little is known about quality of obtained local minima, for a given neighborhood. We concentrate on one of the most difficult optimization problems, the Quadratic Assignment Problem, and we give an upper bound for the quality of solutions obtained with deepest local search. Moreover, other recently established results on the traveling salesman problem, the graph bipartitioning problem and the maximum independent set problem can be deduced as particular cases. (C) 1998 Elsevier Science B.V. All rights reserved.