ON THE QUALITY OF LOCAL SEARCH FOR THE QUADRATIC ASSIGNMENT PROBLEM

Local search is widely used to solve approximately NP-complete combina torial optimization problems. But, little is known about quality of ob tained local minima, for a given neighborhood. We concentrate on one o f the most difficult optimization problems, the Quadratic Assignment P roblem, and we give an upper bound for the quality of solutions obtain ed with deepest local search. Moreover, other recently established res ults on the traveling salesman problem, the graph bipartitioning probl em and the maximum independent set problem can be deduced as particula r cases. (C) 1998 Elsevier Science B.V. All rights reserved.