On Finding and Verifying Locally Optimal Solutions

DOI10.1137/0219052zbMATH Open0697.68041OpenAlexW2031178115MaRDI QIDQ3474886FDOQ3474886

Authors: 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

Recommendations

• How easy is local search?
• A note on the complexity of local search problems
• scientific article; zbMATH DE number 18531
• On the hardness of global and local approximation
• Simple Local Search Problems that are Hard to Solve

zbMATH Keywords

computational complexitylocal searchNP-completePLS

Mathematics Subject Classification ID

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

Cited In (10)

• Finding optimal subgraphs by local search
• Finding robust solutions using local search
• How easy is local search?
• The complexity of Boolean constraint satisfaction local search problems
• Local minima for indefinite quadratic knapsack problems
• Linearizing genomes: exact methods and local search
• Local optimization of dynamic programs with guaranteed satisfaction of path constraints
• Improving TSP tours using dynamic programming over tree decompositions
• The malleability of TSP 2Opt
• A note on the complexity of local search problems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3474886)