Local search, reducibility and approximability of NP-optimization problems

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

zbMATH Keywords

optimizationcomputational complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

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