Reactive local search techniques for the maximum \(k\)-conjunctive constraint satisfaction problem \((MAX-k-CCSP)\)

DOI10.1016/S0166-218X(99)00030-XzbMath0941.68149MaRDI QIDQ1961444

Roberto Battiti, Marco Protasi

Publication date: 3 August 2000

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

Hamming-based reactive tabu search algorithm

Mathematics Subject Classification ID

Searching and sorting (68P10) Nonnumerical algorithms (68W05)

Uses Software

• CCSP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization by Simulated Annealing
• Approximate solution of NP optimization problems
• Local search, reducibility and approximability of NP-optimization problems
• Algorithms for the maximum satisfiability problem
• ``Neural computation of decisions in optimization problems
• How easy is local search?
• Optimization, approximation, and complexity classes
• New local search approximation techniques for maximum generalized satisfiability problems
• Some APX-completeness results for cubic graphs
• Bounding the probability of success of stochastic methods for global optimization
• The continuous reactive tabu search: Blending combinatorial optimization and stochastic search for global optimization
• Tabu Search—Part I
• On Syntactic versus Computational Views of Approximability
• The Reactive Tabu Search
• On the Approximation of Maximum Satisfiability
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Positive linear programming, parallel approximation and PCP's
• Algorithmic aspects in speech recognition
• Reactive local search for the maximum clique problem