Tight bounds on the approximability of almost-satisfiable horn SAT and exact hitting set

Venkatesan Guruswami, Yuan Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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. 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). An instance of Max l-in-/c-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 0(1/log k) for every fixed integer k. This matches (up to constant factors) an easy factor Ω(1/log k;) approximation algorithm for the problem, and resolves a question posed in [GT05]. 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 [Rag08] to conclude that no algorithm can do better than the SDP assuming the UGC. In contrast to previous gap 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.

Original languageEnglish (US)
Title of host publicationProceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011
Pages1574-1589
Number of pages16
StatePublished - May 12 2011
Externally publishedYes
Event22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011 - San Francisco, CA, United States
Duration: Jan 23 2011Jan 25 2011

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011
CountryUnited States
CitySan Francisco, CA
Period1/23/111/25/11

Fingerprint

Hitting Set
Approximability
Assignment
Hardness
Approximation algorithms
Linear programming
Constraint satisfaction problems
Approximation Algorithms
Semidefinite Programming Relaxation
Inapproximability
Linear Programming Relaxation
Subset
Vertex Cover
Integrality
Rounding
Constraint Satisfaction Problem
Intersect
Resolve
Optimality
Game

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this

Guruswami, V., & Zhou, Y. (2011). Tight bounds on the approximability of almost-satisfiable horn SAT and exact hitting set. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011 (pp. 1574-1589). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Tight bounds on the approximability of almost-satisfiable horn SAT and exact hitting set. / Guruswami, Venkatesan; Zhou, Yuan.

Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011. 2011. p. 1574-1589 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Guruswami, V & Zhou, Y 2011, Tight bounds on the approximability of almost-satisfiable horn SAT and exact hitting set. in Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1574-1589, 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, CA, United States, 1/23/11.
Guruswami V, Zhou Y. Tight bounds on the approximability of almost-satisfiable horn SAT and exact hitting set. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011. 2011. p. 1574-1589. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).
Guruswami, Venkatesan ; Zhou, Yuan. / Tight bounds on the approximability of almost-satisfiable horn SAT and exact hitting set. Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011. 2011. pp. 1574-1589 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).
@inproceedings{c763938d30fb4a59abab56883f610851,
title = "Tight bounds on the approximability of almost-satisfiable horn SAT and exact hitting set",
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. 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). An instance of Max l-in-/c-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 0(1/log k) for every fixed integer k. This matches (up to constant factors) an easy factor Ω(1/log k;) approximation algorithm for the problem, and resolves a question posed in [GT05]. 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 [Rag08] to conclude that no algorithm can do better than the SDP assuming the UGC. In contrast to previous gap 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.",
author = "Venkatesan Guruswami and Yuan Zhou",
year = "2011",
month = "5",
day = "12",
language = "English (US)",
isbn = "9780898719932",
series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",
pages = "1574--1589",
booktitle = "Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011",

}

TY - GEN

T1 - Tight bounds on the approximability of almost-satisfiable horn SAT and exact hitting set

AU - Guruswami, Venkatesan

AU - Zhou, Yuan

PY - 2011/5/12

Y1 - 2011/5/12

N2 - 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. 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). An instance of Max l-in-/c-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 0(1/log k) for every fixed integer k. This matches (up to constant factors) an easy factor Ω(1/log k;) approximation algorithm for the problem, and resolves a question posed in [GT05]. 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 [Rag08] to conclude that no algorithm can do better than the SDP assuming the UGC. In contrast to previous gap 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.

AB - 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. 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). An instance of Max l-in-/c-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 0(1/log k) for every fixed integer k. This matches (up to constant factors) an easy factor Ω(1/log k;) approximation algorithm for the problem, and resolves a question posed in [GT05]. 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 [Rag08] to conclude that no algorithm can do better than the SDP assuming the UGC. In contrast to previous gap 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.

UR - http://www.scopus.com/inward/record.url?scp=79955713217&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79955713217&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:79955713217

SN - 9780898719932

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1574

EP - 1589

BT - Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011

ER -