Maximum satisfiability: how good are tabu search and plateau moves in the worst-case?
From MaRDI portal
Publication:1779533
DOI10.1016/j.ejor.2003.01.005zbMath1066.90048MaRDI QIDQ1779533
Luca Maria Gambardella, Monaldo Mastrolilli
Publication date: 1 June 2005
Published in: European Journal of Operational Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ejor.2003.01.005
90C60: Abstract computational complexity for mathematical programming problems
90B40: Search theory
90C59: Approximation methods and heuristics in mathematical programming
90C40: Markov and semi-Markov decision processes
Related Items
A heuristic algorithm for hierarchical hub-and-spoke network of time-definite common carrier operation planning problem, A Theoretical Analysis of Search in GSAT
Uses Software
Cites Work
- Algorithms for the maximum satisfiability problem
- Future paths for integer programming and links to artificial intelligence
- Effective neighbourhood functions for the flexible job shop problem
- Guided local search for solving SAT and weighted MAX-SAT problems
- Applying tabu search to the job-shop scheduling problem
- Tabu Search—Part I
- Tabu Search—Part II
- 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
- Algorithmic aspects in speech recognition
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item