Local search, reducibility and approximability of NP-optimization problems
From MaRDI portal
Publication:673464
DOI10.1016/0020-0190(95)00006-XzbMath1022.68561OpenAlexW1975220965MaRDI QIDQ673464
Marco Protasi, Giorgio Ausiello
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
Related Items
New local search approximation techniques for maximum generalized satisfiability problems, Analyzing the complexity of finding good neighborhood functions for local search algorithms, Metaheuristics: A bibliography, Finding optimal subgraphs by local search, Non-oblivious local search for graph and hypergraph coloring problems, Reactive local search techniques for the maximum \(k\)-conjunctive constraint satisfaction problem \((MAX-k-CCSP)\), Evolutionary algorithms and dynamic programming, Approximate solution of NP optimization problems, COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES, Local search for the minimum label spanning tree problem with bounded color classes., Hitting times of local and global optima in genetic algorithms with very high selection pressure
Cites Work
- Approximate solution of NP optimization problems
- Completeness in approximation classes
- How easy is local search?
- Structure preserving reductions among convex optimization problems
- Toward a unified approach for the classification of NP-complete optimization problems
- Non deterministic polynomial optimization problems and their approximations
- Optimization, approximation, and complexity classes
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
