Tight Bounds on the Approximability of Almost-Satisfiable Horn SAT and Exact Hitting Set

by Venkatesan Guruswami and Yuan Zhou

Theory of Computing, Volume 8(11), pp. 239-267, 2012

Bibliography with links to cited articles

[1]   Libor Barto and Marcin Kozik: Constraint satisfaction problems of bounded width. In Proc. 50th FOCS, pp. 595–603. IEEE Comp. Soc. Press, October 2009. [doi:10.1109/FOCS.2009.32]

[2]   Libor Barto and Marcin Kozik: Robust satisfiability of constraint satisfaction problems. In Proc. 44th STOC, pp. 931–940. ACM Press, 2012. [doi:10.1145/2213977.2214061]

[3]   Moses Charikar, Konstantin Makarychev, and Yury Makarychev: Near-optimal algorithms for unique games. In Proc. 38th STOC, pp. 205–214. ACM Press, 2006. [doi:10.1145/1132516.1132547]

[4]   Moses Charikar, Konstantin Makarychev, and Yury Makarychev: Near-optimal algorithms for maximum constraints satisfaction problems. ACM Trans. Algorithms, 5(3), 2009. Preliminary version in SODA’07. [doi:10.1145/1541885.1541893]

[5]   Pierluigi Crescenzi, Riccardo Silvestri, and Luca Trevisan: On weighted vs unweighted versions of combinatorial optimization problems. Inform. and Comput., 167(1):10–26, 2001. Preliminary version in ISTCS’96. [doi:10.1006/inco.2000.3011]

[6]   Victor Dalmau and Andrei Krokhin: Robust satisfiability for CSPs: Algorithmic and hardness results, 2011. In preparation.

[7]   Erik D. Demaine, Uriel Feige, Mohammad Taghi Hajiaghayi, and Mohammad R. Salavatipour: Combination can be hard: Approximability of the unique coverage problem. SIAM J. Comput., 38(4):1464–1483, 2008. Preliminary version in SODA’06. [doi:10.1137/060656048]

[8]   Venkatesan Guruswami and Luca Trevisan: The complexity of making unique choices: Approximating 1-in-k sat. In Proc. 8th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’05), pp. 99–110, 2005. [doi:10.1007/11538462_9]

[9]   Johan Hĺstad: Some optimal inapproximability results. J. ACM, 48(4):798–859, 2001. Preliminary version in STOC’97. [doi:10.1145/502090.502098]

[10]   Pavol Hell and Jaroslav Nešetřil: Colouring, constraint satisfaction, and complexity. Comp. Sci. Rev., 2(3):143–163, 2008. [doi:10.1016/j.cosrev.2008.10.003]

[11]   Peter Jonsson, Andrei Krokhin, and Fredrik Kuivinen: Hard constraint satisfaction problems have hard gaps at location 1. Theoret. Comput. Sci., 410(38-40):3856–3874, 2009. [doi:j.tcs.2009.05.022]

[12]   Sanjeev Khanna, Madhu Sudan, Luca Trevisan, and David P. Williamson: The approximability of constraint satisfaction problems. SIAM J. Comput., 30(6):1863–1920, 2001. [doi:10.1137/S0097539799349948]

[13]   Subhash Khot: On the power of unique 2-prover 1-round games. In Proc. 34th STOC, pp. 767–775. ACM Press, 2002. [doi:10.1145/509907.510017]

[14]   Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell: Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput., 37(1):319–357, 2007. Preliminary version in FOCS’04. [doi:10.1137/S0097539705447372]

[15]   Subhash Khot and Oded Regev: Vertex cover might be hard to approximate to within 2-ϵ. J. Comput. System Sci., 74(3):335–349, 2008. Preliminary version in CCC’03. [doi:10.1016/j.jcss.2007.06.019]

[16]   Gábor Kun, Ryan O’Donnell, Suguru Tamaki, Yuichi Yoshida, and Yuan Zhou: Linear programming, width-1 CSPs, and robust satisfaction. In Proc. 3rd Innovations in Theoretical Computer Science Conf. (ITCS’12), pp. 484–495, New York, NY, USA, 2012. ACM Press. [doi:10.1145/2090236.2090274]

[17]   Prasad Raghavendra: Optimal algorithms and inapproximability results for every CSP? In Proc. 40th STOC, pp. 245–254. ACM Press, 2008. [doi:10.1145/1374376.1374414]

[18]   Thomas J. Schaefer: The complexity of satisfiability problems. In Proc. 10th STOC, pp. 216–226. ACM Press, 1978. [doi:10.1145/800133.804350]

[19]   Uri Zwick: Finding almost-satisfying assignments. In Proc. 30th STOC, pp. 551–560. ACM Press, 1998. [doi:10.1145/276698.276869]