Theory of Computing
-------------------
Title     : Tight Bounds on the Approximability of Almost-Satisfiable Horn SAT and Exact Hitting Set
Authors   : Venkatesan Guruswami and Yuan Zhou
Volume    : 8
Number    : 11
Pages     : 239-267
URL       : https://theoryofcomputing.org/articles/v008a011

Abstract
--------

  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 - \epsilon) of its constraints for some small constant
  \epsilon > 0, it is hard to find an assignment satisfying more than
  (1 - 1/O(log (1 / \epsilon))) of the constraints. This matches a linear
  programming based algorithm due to Zwick (STOC 1998), resolving the
  natural open question raised in that work concerning the optimality
  of the approximation bound.

  Given a (1 - \epsilon)-satisfiable instance of Max Horn-2SAT for
  some constant \epsilon > 0, it is possible to find a (1 - 2\epsilon)-
  satisfying assignment efficiently. This improves the algorithm given 
  in Khanna et al. (2000) which finds a (1 - 3\epsilon)-satisfying 
  assignment, and also matches the (1 - c\epsilon) 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 size at most k, and the goal is
  to find a subset of U that intersects the maximum number of sets
  in C at a unique element. We prove that Max 1-in-k-HS 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 in Guruswami and Trevisan (APPROX 2005).

  It is crucial for the above hardness that sets of size up to k
  are allowed; indeed, when all sets have size k, there is a simple
  factor 1/e-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. In
  contrast to previous such constructions where the instances had a
  good SDP solution by design and the main task was bounding the
  integral optimum, the challenge in our case is the construction
  of appropriate SDP vectors and the integral optimum is easy to
  bound.  Our algorithmic results are based on rounding appropriate
  linear programming relaxations.