Title :
On finding locally optimal solutions
Author :
Krentel, Mark W.
Author_Institution :
Dept. of Comput Sci., Rice Univ., Houston, TX, USA
Abstract :
The problem of finding locally optimal solutions to combinatorial problems in the framework of polynomial-time local search as defined by D.S. Johnson et al. (J. Comput. Syst. Sci., vol.37, no.1, p.79-100, Aug. 1988) is considered. A PLS-complete problem such that the problem of verifying local optimality can be solved in LOGSPACE is exhibited. For all previously known PLS-complete problems, verifying local optimality was P-complete, and it was conjectured in Johnson et al. that this was necessary
Keywords :
algorithm theory; search problems; LOGSPACE; PLS-complete problem; combinatorial problems; local optimality; locally optimal solutions; polynomial-time local search; Computer science; Cost function; Optimized production technology; Partitioning algorithms; Polynomials; Search problems;
Conference_Titel :
Structure in Complexity Theory Conference, 1989. Proceedings., Fourth Annual
Conference_Location :
Eugene, OR
Print_ISBN :
0-8186-1958-9
DOI :
10.1109/SCT.1989.41819
