Maximum satisfiability: how good are tabu search and plateau moves in the worst-case?

DOI10.1016/j.ejor.2003.01.005zbMath1066.90048OpenAlexW2158185647MaRDI QIDQ1779533

Monaldo Mastrolilli, Luca Maria Gambardella

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

zbMATH Keywords

Tabu searchLocal searchWorst-case analysisMaximum satisfiability

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Search theory (90B40) Approximation methods and heuristics in mathematical programming (90C59) Markov and semi-Markov decision processes (90C40)

Related Items

An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem ⋮ 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

• MAX-2-SAT
• Walksat

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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