Simple local search problems that are hard to solve

Simple local search problems that are hard to solve

0.00 Avg rating0 Votes
Article ID: iaor19981356
Country: United States
Volume: 20
Issue: 1
Start Page Number: 56
End Page Number: 87
Publication Date: Jan 1991
Journal: SIAM Journal On Computing
Authors: ,
Keywords: programming: network, networks: path, computational analysis
Abstract:

Many algorithms for NP-hard optimization problems find solutions that are locally optimal, in the sense that the solutions cannot be improved by a polynomially computable perturbation. Very little is known about the complexity of finding locally optimal solutions, either by local search algorithms or using other indirect methods. Johnson, Papadimitriou, and Yannakakis studied this question by defining a complexity class PLS that captures local search problems. It was proved that finding a partition of a graph that is locally optimal into equal parts with respect to the acclaimed Kernighan–Lin algorithm is PLS-complete. It is shown here that several natural, simple local search problems are PLS-complete, and thus just as hard. Two examples are: finding a partition that cannot be improved by a single swap of two vertices, and finding a stable configuration for an undirected connectionist network. When edges or other objects are unweighted, then a local optimum can always be found in polynomial time. It is shown that the unweighted versions of the local search problems studied in this paper are P-complete.

Reviews

Required fields are marked *. Your email address will not be published.