Solving MAX-r-SAT Above a Tight Lower Bound |
| |
| Authors: | Noga Alon Gregory Gutin Eun Jung Kim Stefan Szeider Anders Yeo |
| |
| Affiliation: | 1.Schools of Mathematics and Computer Science,Tel Aviv University,Tel Aviv,Israel;2.Department of Computer Science, Royal Holloway,University of London,Egham,UK;3.Institute of Information Systems,Vienna University of Technology,Vienna,Austria |
| |
| Abstract: | We present an exact algorithm that decides, for every fixed r≥2 in time O(m)+2O(k2)O(m)+2^{O(k^{2})} whether a given multiset of m clauses of size r admits a truth assignment that satisfies at least ((2 r −1)m+k)/2 r clauses. Thus Max-r-Sat is fixed-parameter tractable when parameterized by the number of satisfied clauses above the tight lower bound (1−2−r )m. This solves an open problem of Mahajan et al. (J. Comput. Syst. Sci. 75(2):137–153, 2009). |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
