DocumentCode :
2130465
Title :
Structure in locally optimal solutions
Author :
Krentel, M.W.
Author_Institution :
Dept. of Comput. Sci., Rice Univ., Houston, TX
fYear :
1989
fDate :
30 Oct-1 Nov 1989
Firstpage :
216
Lastpage :
221
Abstract :
A class of local search problems, PLS (polynomial-time local search), as defined by D.S. Johnson et al. (see J. Comput. Syst. Sci., vol.37, no.1, p.79-100 (1988)) is considered. PLS captures much of the structure of NP problems at the level of their feasible solutions and neighborhoods. It is first shown that CNF (conjunctive normal form) satisfiability is PLS-complete, even with simultaneously bounded size clauses and bounded number of occurrences of variables. This result is used to show that traveling salesman under the k-opt neighborhood is also PLS-complete. It is argued that PLS-completeness is the normal behavior of NP-complete problems
Keywords :
computational complexity; search problems; NP problems; PLS; conjunctive normal form; local search problems; locally optimal solution structure; polynomial-time local search; traveling salesman; Circuits; Computer science; Cost function; NP-complete problem; Partitioning algorithms; Polynomials; Search problems;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 1989., 30th Annual Symposium on
Conference_Location :
Research Triangle Park, NC
Print_ISBN :
0-8186-1982-1
Type :
conf
DOI :
10.1109/SFCS.1989.63481
Filename :
63481
Link To Document :
بازگشت