On Finding and Verifying Locally Optimal Solutions

DOI10.1137/0219052MaRDI QIDQ3474886zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

computational complexitylocal searchNP-completePLS

Mathematics Subject Classification ID

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

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

Cited in

(14)

• How easy is local search?
• Local minima for indefinite quadratic knapsack problems
• Finding optimal subgraphs by local search
• The complexity of Boolean constraint satisfaction local search problems
• Finding robust solutions using local search
• Linearizing genomes: exact methods and local search
• Improving TSP tours using dynamic programming over tree decompositions
• The malleability of TSP 2Opt
• A note on the complexity of local search problems
• The k-Opt algorithm for the traveling salesman problem has exponential running time for k 5
• The complexity of computing KKT solutions of quadratic programs
• Separations in proof complexity and TFNP
• Settling the complexity of Nash equilibrium in congestion games
• Local optimization of dynamic programs with guaranteed satisfaction of path constraints

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)