On Finding and Verifying Locally Optimal Solutions

DOI10.1137/0219052zbMath0697.68041OpenAlexW2031178115MaRDI QIDQ3474886

Mark W. Krentel

Publication date: 1990

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0219052

zbMATH Keywords

computational complexitylocal searchNP-completePLS

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (7)

Finding optimal subgraphs by local search ⋮ The malleability of TSP 2Opt ⋮ Linearizing Genomes: Exact Methods and Local Search ⋮ Local minima for indefinite quadratic knapsack problems ⋮ A note on the complexity of local search problems ⋮ The complexity of Boolean constraint satisfaction local search problems ⋮ Improving TSP Tours Using Dynamic Programming over Tree Decompositions.

This page was built for publication: On Finding and Verifying Locally Optimal Solutions