Opening book details…
Can I read On the classification of NP-complete problems in terms of their correlation coefficient on EtoBox?
On the classification of NP-complete problems in terms of their correlation coefficient by Eric Angel; Vassilis Zissimopoulos is a Computer Science article available to read on EtoBox.
What is On the classification of NP-complete problems in terms of their correlation coefficient about?
Local search and its variants simulated annealing and tabu search are very popular metaheuristics to approximatively 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 coe cient, 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 ÿrst 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 classiÿcation with experimental results reported in the liter
Who reads On the classification of NP-complete problems in terms of their correlation coefficient?
It is typically read by researchers, students, and practitioners in Computer Science.
- Author
- Eric Angel; Vassilis Zissimopoulos
- Publisher
- Elsevier Science; Elsevier ; Elsevier BV (ISSN 0166-218X)
- Published
- 2000
- Language
- EN
- Field
- Computer Science (Physical Sciences)