A note on the complexity of local search problems

DOI10.1016/0020-0190(94)00184-ZMaRDI QIDQ673814zbMATH OpenOpenAlexWikidataFDO

Authors Sophie Fischer

Publication date 28 February 1997

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(94)00184-z

zbMATH Keywords

Local searchCombinatorial problemsTheory of computation

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Searching and sorting (68P10)

Recommendations

• How easy is local search?
• scientific article; zbMATH DE number 18531
• Simple Local Search Problems that are Hard to Solve
• Local search: simple, successful, but sometimes sluggish

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• How easy is local search?
• On Finding and Verifying Locally Optimal Solutions
• Simple Local Search Problems that are Hard to Solve
• The Complexity of the Lin–Kernighan Heuristic for the Traveling Salesman Problem

Cited in

(20)

• On the complexity of the local search in the \(p\)-median problem
• On Finding and Verifying Locally Optimal Solutions
• Local search, reducibility and approximability of NP-optimization problems
• The complexity of Boolean constraint satisfaction local search problems
• On Search Problems in Complexity Theory and in Logic (Abstract)
• Metaheuristics: A bibliography
• Local search: simple, successful, but sometimes sluggish
• On the complexity of local search for weighted standard set problems
• Analyzing the complexity of finding good neighborhood functions for local search algorithms
• Local search and the local structure of NP-complete problems
• Computational bounds for local search in combinatorial optimization
• Complexity of local search for the \(p\)-median problem
• The communication complexity of local search
• On the \(\mathcal {PLS}\)-complexity of maximum constraint assignment
• On the query complexity of finding a local maximum point.
• Simple Local Search Problems that are Hard to Solve
• Nested PLS
• How easy is local search?
• Note on constrained long choice with multiple beginning elements
• scientific article; zbMATH DE number 18531 (Why is no real title available?)

This page was built for publication: A note on the complexity of local search problems

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