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]