## The Parameterized Complexity of k-Flip Local Search for SAT and MAX SATDiscrete Optimization, vol. 8, pp. 139-145, 2011.
Preliminary version appeared in the proceedings of SAT 2009, Lecture Notes in Computer Science, vol. 5584, pp. 276-283, Springer, 2009. ## Abstract:SAT and MAX SAT are among the most prominent problems for which local search algorithms have been successfully applied. A fundamental task for such an algorithm isk-flip local
search, to increase the number of clauses satisfied by a given
truth assignment by flipping the truth values of at most k
variables. For a total number of n variables the size of
the search space is of order n and grows
quickly in ^{k}k; hence most practical algorithms
use 1-flip local search only.
In this paper we investigate the worst-case complexity of k-flip local search,
considering k as a parameter: is it possible to search
significantly faster than the trivial n bound?
In addition to the unbounded case we consider instances with a
bounded number of literals per clause or where each variable
occurs in a bounded number of clauses. We also consider the
related problem that asks whether we can satisfy ^{k}all
clauses by flipping at most k variables.
Download: [paper pdf] [back to Stefan Szeider's homepage] |