On the classification of NP-complete problems in terms of their correlation coefficient

On the classification of NP-complete problems in terms of their correlation coefficient

0.00 Avg rating0 Votes
Article ID: iaor20012916
Country: Netherlands
Volume: 99
Issue: 1/3
Start Page Number: 261
End Page Number: 277
Publication Date: Feb 2000
Journal: Discrete Applied Mathematics
Authors: ,
Keywords: heuristics
Abstract:

Local search and its variants simulated annealing and tabu search are very popular meta-heuristics to approximately solve NP-hard optimization problems. Several experimental studies in the literature have shown that in practice some problems (e.g. the Traveling Salesman Problem, Quadratic Assignment Problem) behave very well with these heuristics, whereas others do not (e.g. the Low Autocorrelation Binary String Problem). The autocorrelation function, introduced by Weinberger, measures the ruggedness of a landscape which is formed by a cost function and a neighborhood. We use a derived parameter, named the autocorrelation coefficient, as a tool to better understand these phenomena. In this paper we mainly study cost functions including penalty terms. Our results can be viewed as a first attempt to theoretically justify why it is often better in practice to enlarge the solution space and add penalty terms than to work solely on feasible solutions. Moreover, some new results as well as previously known results allow us to obtain a hierarchy of combinatorial optimization problems relatively to their ruggedness. Comparing this classification with experimental results reported in the literature yields a good agreement between ruggedness and difficulty for local search methods. In this way, we are also able to justify theoretically why a neighborhood is better than another for a given problem.

Reviews

Required fields are marked *. Your email address will not be published.