Name
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 [J. Comput. System Sci., 37 (1988), pp. 79-100] 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. |
Year | DOI | Venue |
|---|---|---|
1991 | 10.1137/0220004 | SIAM J. Comput. |
Keywords | Field | DocType |
simple local search problem,local search,satisfiability,graph partitioning,max cut,local optima,algorithms | Complexity class,Discrete mathematics,Combinatorics,Vertex (geometry),Local optimum,Satisfiability,Local search (optimization),Graph partition,Optimization problem,Maximum cut,Mathematics | Journal |
Volume | Issue | ISSN |
20 | 1 | 0097-5397 |
Citations | PageRank | References |
89 | 11.52 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alejandro A. Schäffer | 1 | 827 | 136.66 |
| Mihalis Yannakakis | 2 | 11141 | 2069.50 |