Yagiura and Ibaraki 
 

Most Stochastic Local Search (SLS) algorithms for Propositional
Satisfiability are based on a "1-flip neighbourhood" - that is, each
step in the algorithm involves flipping only one propositional variable
which is chosen according to some heuristic.  In their paper, Yagiura
and Ibaraki examine the effects of using larger neighbourhoods on the
performance of various algorithms for MaxSAT.  I will describe their
algorithm and the techniques which they use for their efficient
implementation, and then briefly contrast this with some of the research
that has been going on in the Beta Lab on MaxSAT.