Local search, reducibility and approximability of NP-optimization problems
From MaRDI portal
Publication:673464
DOI10.1016/0020-0190(95)00006-XzbMATH Open1022.68561OpenAlexW1975220965MaRDI QIDQ673464FDOQ673464
Authors: Giorgio Ausiello, Marco Protasi 
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(95)00006-x
Recommendations
- Local search and the local structure of NP-complete problems
- scientific article; zbMATH DE number 861333
- Local search: complexity and approximation
- A note on the complexity of local search problems
- Computational bounds for local search in combinatorial optimization
- Approximate local search in combinatorial optimization
- Approximate Local Search in Combinatorial Optimization
- scientific article; zbMATH DE number 1944142
- A Survey of Approximation Results for Local Search Algorithms
- scientific article; zbMATH DE number 847149
Cites Work
- Title not available (Why is that?)
- Optimization, approximation, and complexity classes
- Structure preserving reductions among convex optimization problems
- How easy is local search?
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximate solution of NP optimization problems
- Completeness in approximation classes
- Non deterministic polynomial optimization problems and their approximations
- Title not available (Why is that?)
- Title not available (Why is that?)
- Toward a unified approach for the classification of NP-complete optimization problems
Cited In (12)
- Non-oblivious local search for graph and hypergraph coloring problems
- Finding optimal subgraphs by local search
- Reactive local search techniques for the maximum \(k\)-conjunctive constraint satisfaction problem \((MAX-k-CCSP)\)
- Analyzing the complexity of finding good neighborhood functions for local search algorithms
- Approximate solution of NP optimization problems
- COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES
- Evolutionary algorithms and dynamic programming
- Metaheuristics: A bibliography
- Hitting times of local and global optima in genetic algorithms with very high selection pressure
- Local search for the minimum label spanning tree problem with bounded color classes.
- New local search approximation techniques for maximum generalized satisfiability problems
- Simple Local Search Problems that are Hard to Solve
This page was built for publication: Local search, reducibility and approximability of NP-optimization problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q673464)
