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

Abstract

Tabu search algorithms are amongst the most successful local search based methods for the maximum satisfiability prob-lem. 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 parame-ter 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 advan-tage of a tabu search strategy over the basic local search alone that critically depends on the tabu list length.