A New Lower Bound on the Maximum Number of Satisfied Clauses in Max-SAT and its Algorithmic Applications

R. Crowston, G. Gutin, M. Jones +1

A pair of unit clauses is called conflicting if it is of the form $(x)$, $(\bar{x})$. A CNF formula is unit-conflict free (UCF) if it contains no pair of conflicting unit clauses.…