Tight bounds on the approximability of almost-satisfiable Horn SAT and exact hitting set
Venkatesan Guruswami, Yuan Zhou · 2011
We study the approximability of two natural Boolean constraint satisfaction problems: Horn satisfiability and exact hitting set. Under the Unique Games conjecture, we prove the following optimal inapproximability and approximability results for finding an assignment satisfying as many constraints as possible given a near-satisfiable instance. 1. Given an instance of Max Horn-3SAT that admits an assignment satisfying (1 − ε) of its constraints for some small constant ε> 0, it is hard to find an assignment satisfying more than (1 − 1/O(log(1/ε))) of the constraints. This matches a linear programming based algorithm due to Zwick [Zwi98], resolving the natural open question raised in that work concerning the optimality of the approximation bound. Given a (1 − ε) satisfiable instance of Max Horn-2SAT for some constant ε> 0, it is possible to find a (1 − 2ε)-satisfying assignment efficiently. This improves the algorithm given in [KSTW00] which finds a (1−3ε)-satisfying assignment, and also matches the (1−cε) hardness for any c < 2 derived from vertex cover (under UGC). 2. An instance of Max 1-in-k-HS consists of a universe U and a collection C of subsets of U of