期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2010
卷号：2010
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 {\em
near-satisfiable} instance.
\begin{enumerate}
\item Given an instance of \hornthreesat\ that admits an assignment satisfying (1−\eps) of its constraints for some small constant
\eps0, it is hard to find an assignment satisfying more than (1−1O(log(1\eps))) of the constraints. This matches a linear
programming based algorithm due to Zwick (1998), resolving the natural open question raised in that work concerning the optimality of the approximation bound.
Given a (1−\eps) satisfiable instance of {\sf Max Horn-2SAT} for some constant \eps0, one can find a (1−2\eps)-satisfying assignment efficiently. This improves the algorithm given by Khanna, Sudan, Trevisan, and Williamson (2000) which finds a (1−3\eps)-satisfying assignment, and also matches the (1−c\eps) hardness for any c2 derived from vertex cover (under UGC).
