Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > TOTAL SEARCH PROBLEMS:
Reports tagged with Total Search Problems:
TR03-051 | 20th June 2003
Tsuyoshi Morioka

The Relative Complexity of Local Search Heuristics and the Iteration Principle

Johnson, Papadimitriou and Yannakakis introduce the class $\PLS$
consisting of optimization problems for which efficient local-
search heuristics exist. We formulate a type-2 problem $\iter$
that characterizes $\PLS$ in style of Beame et al., and prove
a criterion for type-2 problems to be nonreducible to $\iter$.
As a corollary, ... more >>>




ISSN 1433-8092 | Imprint