Approximation Algorithm for Non-Boolean Max-$k$-CSP

by Konstantin Makarychev and Yury Makarychev

Theory of Computing, Volume 10(13), pp. 341-358, 2014

Bibliography with links to cited articles

[1]   Per Austrin and Elchanan Mossel: Approximation resistant predicates from pairwise independence. Comput. Complexity, 18(2):249–271, 2009. Preliminary version in CCC’08. [doi:10.1007/s00037-009-0272-6]

[2]   Siu On Chan: Approximation resistance from pairwise independent subgroups. In Proc. 45th STOC, pp. 447–456. ACM Press, 2013. [doi:10.1145/2488608.2488665]

[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 constraint satisfaction problems. ACM Trans. Algorithms, 5(32), 2009. Preliminary version in SODA’07. [doi:10.1145/1541885.1541893]

[5]   Eden Chlamtáč, Konstantin Makarychev, and Yury Makarychev: How to play unique games using embeddings. In Proc. 47th FOCS, pp. 687–696. IEEE Comp. Soc. Press, 2006. [doi:10.1109/FOCS.2006.36]

[6]   Lars Engebretsen: The nonapproximability of non-boolean predicates. SIAM J. Discrete Math., 18(1):114–129, 2004. Preliminary version in RANDOM’01. [doi:10.1137/S0895480100380458]

[7]   Lars Engebretsen and Jonas Holmerin: More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP. Random Struct. Algorithms, 33(4):497–514, 2008. Preliminary version in STACS’05. [doi:10.1002/rsa.20226]

[8]   Venkatesan Guruswami and Prasad Raghavendra: Constraint satisfaction over a non-Boolean domain: Approximation algorithms and Unique-Games hardness. In Proc. 12th Internat. Workshop on Randomization and Computation (RANDOM’08), pp. 77–90. Springer, 2008. [doi:10.1007/978-3-540-85363-3_7]

[9]   Gustav Hast: Approximating Max kCSP — outperforming a random assignment with almost a linear factor. In Proc. 32th Internat. Colloq. on Automata, Languages and Programming (ICALP’05), pp. 956–968. Springer, 2005. [doi:10.1007/11523468_77]

[10]   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]

[11]   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]

[12]   Alex Samorodnitsky and Luca Trevisan: A PCP characterization of NP with optimal amortized query complexity. In Proc. 32nd STOC, pp. 191–199. ACM Press, 2000. [doi:10.1145/335305.335329]

[13]   Alex Samorodnitsky and Luca Trevisan: Gowers uniformity, influence of variables, and PCPs. In Proc. 38th STOC, pp. 11–20. ACM Press, 2006. [doi:10.1145/1132516.1132519]

[14]   Luca Trevisan: Parallel approximation algorithms by positive linear programming. Algorithmica, 21(1):72–88, 1998. Preliminary version in ESA’96. [doi:10.1007/PL00009209]

[15]   Zbyněk Šidák: Rectangular confidence regions for the means of multivariate normal distributions. Journal of the American Statistical Association, 62(318):626–633, 1967. [doi:10.2307/2283989]