A New Bound for 3-Satisfiable MaxSat and its Algorithmic Application

Gregory Gutin, Mark Jones, Dominik Scheder +1

Let F be a CNF formula with n variables and m clauses. F is 3-satisfiable if for any 3 clauses in F, there is a truth assignment which satisfies all of them. Lieberherr and Specker…