How easy is local search

摘要: We investigate the complexity of finding locally optimal solutions to NP-hard combinatorial optimization problems. Local optimality arises in context local search algorithms, which try find improved by considering perturbations current solution (“neighbors” that solution). If no neighboring is better than solution, it optimal. Finding presumably easier solutions. Nevertheless, many popular algorithms are based on neighborhood structures for not known be computable polynomial time, either using themselves or taking some indirect route. define a natural class PLS consisting essentially those problems can verified and show there complete this class. In particular, partition graph with respect well-known Kernighan-Lin algorithm partitioning PLS-complete, hence accomplished time only if optima found all PLS.