ECCC-Report TR10-063https://eccc.weizmann.ac.il/report/2010/063Comments and Revisions published for TR10-063en-usMon, 17 May 2010 16:24:31 +0300
Revision 1
| Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set |
Venkatesan Guruswami,
Yuan Zhou
https://eccc.weizmann.ac.il/report/2010/063#revision1 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
$\eps > 0$, it is hard to find an assignment satisfying more than $(1-1/O(\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 $\eps > 0$, 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 $c < 2$ derived from vertex cover (under UGC).
\item An instance of 1-in-k-Hitting-Set consists of a universe $U$ and a collection $\mathcal{C}$ of subsets of $U$ of size at most $k$, and the goal is to find a subset of $U$ that intersects the maximum number of sets in $\mathcal{C}$ at a unique element. We prove that this problem is hard to approximate within a factor of $O(1/\log k)$ for every fixed integer $k$. This matches (up to constant factors) an easy factor $\Omega(1/\log k)$ approximation algorithm for the problem, and resolves a question posed by Guruswami and Trevisan (2005).
It is crucial for the above hardness that sets of size {\em up to} $k$ are allowed; indeed, when all sets have size $k$, there is a
simple factor $1/e$-approximation algorithm.
Moreover, the hardness applies when the instance admits a solution satisfying $1-1/k^{0.99}$ of the constraints. In contrast, for instances which are $(1-\frac{1}{1.01 k})$-satisfiable, we give a constant factor approximation algorithm.
Our hardness results are proved by constructing integrality gap instances for a semidefinite programming relaxation for the problems,
and using Raghavendra's result (STOC 2008) to conclude that no algorithm can do better than the SDP assuming the UGC. The algorithmic results are based on rounding appropriate linear programming relaxations.
Mon, 17 May 2010 16:24:31 +0300https://eccc.weizmann.ac.il/report/2010/063#revision1
Paper TR10-063
| Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set} |
Venkatesan Guruswami,
Yuan Zhou
https://eccc.weizmann.ac.il/report/2010/063 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
$\eps > 0$, it is hard to find an assignment satisfying more than $(1-1/O(\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 $\eps > 0$, 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 $c < 2$ derived from vertex cover (under UGC).
\item An instance of 1-in-k-Hitting-Set consists of a universe $U$ and a collection $\mathcal{C}$ of subsets of $U$ of size at most $k$, and the goal is to find a subset of $U$ that intersects the maximum number of sets in $\mathcal{C}$ at a unique element. We prove that this problem is hard to approximate within a factor of $O(1/\log k)$ for every fixed integer $k$. This matches (up to constant factors) an easy factor $\Omega(1/\log k)$ approximation algorithm for the problem, and resolves a question posed by Guruswami and Trevisan (2005).
It is crucial for the above hardness that sets of size {\em up to} $k$ are allowed; indeed, when all sets have size $k$, there is a
simple factor $1/e$-approximation algorithm.
Moreover, the hardness applies when the instance admits a solution satisfying $1-1/k^{0.99}$ of the constraints. In contrast, for instances which are $(1-\frac{1}{1.01 k})$-satisfiable, we give a constant factor approximation algorithm.
Our hardness results are proved by constructing integrality gap instances for a semidefinite programming relaxation for the problems,
and using Raghavendra's result (STOC 2008) to conclude that no algorithm can do better than the SDP assuming the UGC. The algorithmic results are based on rounding appropriate linear programming relaxations.
Mon, 12 Apr 2010 17:58:33 +0300https://eccc.weizmann.ac.il/report/2010/063