Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, January 11, 2005, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Christopher Portmann
Tabu search algorithms are amongst the most successful local search based methods for the maximum satisfiability problem. The pratical superiority of tabu search over local search alone has been already shown experimentally several times. Two questions that arise, are whether this holds in the worst case and how large should the tabu list length be. In this talk we will focus on MAX-2-SAT. I will show that for any instance with n variables tabu search performs better than a basic local search, if the tabu list lenghth is at least n, but not otherwise.
Source: M. Mastrolilli and L. M. Gambardella, Maximum satisfiability: How good are tabu search and plateau moves in the worst-case?, European Journal of Operational Research, to appear.
Automatic MiSe System Software Version 1.4803M | admin login