کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1141541 | 957018 | 2011 | 7 صفحه PDF | دانلود رایگان |
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 is to increase the number of clauses satisfied by a given truth assignment by flipping the truth values of at most kk variables (kk-flip local search). For a total number of nn variables the size of the search space is of order nknk and grows quickly in kk; hence most practical algorithms use 1-flip local search only. In this paper we investigate the worst-case complexity of kk-flip local search, considering kk as a parameter: is it possible to search significantly faster than the trivial nknk bound? In addition to the unbounded case we consider instances with a bounded number of literals per clause and instances where each variable occurs in a bounded number of clauses. We also consider the related problem that asks whether we can satisfy all clauses by flipping the truth values of at most kk variables.
Journal: Discrete Optimization - Volume 8, Issue 1, February 2011, Pages 139–145