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

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

zbMATH Keywords

Tabu search; Local search; Worst-case analysis; Maximum satisfiability

Mathematics Subject Classification ID

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

• 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