 |
 |
********************************************************* Max2Sat: How good is tabu search in the worst-case? By Monaldo Mastrolilli and Luca Maria Gambardella ********************************************************* The practical superiority of tabu search over 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. Focusing on MAX-2-SAT problem, we give the 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. Please find this paper for downloading at: http://www.idsia.ch/~monaldo/publications.html ========================== Monaldo Mastrolilli, Ph.D. IDSIA - Istituto Dalle Molle di Studi sull' Intelligenza Artificiale Email: [log in to unmask] http://www.idsia.ch/~monaldo