MAX-2-SAT: How Good Is Tabu Search in the Worst-Case?
Monaldo MastrolilliLuca Maria GambardellaPublished in: AAAI (2004)
Keyphrases
- max sat
- tabu search
- worst case
- lower bound
- simulated annealing
- scheduling problem
- metaheuristic
- weighted max sat
- feasible solution
- upper bound
- exact algorithms
- np hard
- memetic algorithm
- search algorithm
- path relinking
- hybrid algorithm
- job shop scheduling problem
- heuristic methods
- genetic algorithm
- stochastic local search
- scatter search
- search procedure
- max sat solver
- branch and bound algorithm
- tabu list
- boolean satisfiability
- maximum satisfiability
- initial solution
- approximation algorithms
- vehicle routing problem
- quadratic assignment problem
- hill climbing
- computational complexity
- tabu search algorithm
- search space
- dynamic programming
- orders of magnitude
- iterated local search
- combinatorial optimization
- search strategy
- sat solvers
- neural network