MAX-2-SAT: How Good Is Tabu Search in the Worst-Case?

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 19

Constraint Satisfaction and Satisfiability

Tabu search algorithms are amongst the most successful local search based methods for the maximum satisfiability problem. The practical superiority of tabu search over the local search alone has been already shown experimentally several times. A natural question addressed here is to understand if this superiority holds also from the worst-case point of view. Moreover, it is well known that the main critical parameter of tabu techniques is the tabu list length. Focussing on MAX-2-SAT problem, the main contribution of this paper is a worst-case analysis of tabu search as a function of the tabu list length. We give a first theoretical evidence of the advantage of a tabu search strategy over the basic local search alone that critically depends on the tabu list length.