Improved Inapproximability Results for Maximum $k$-Colorable Subgraph
by Venkatesan Guruswami and Ali Kemal Sinop
Theory of Computing, Volume 9(11), pp. 413-435, 2013
Bibliography with links to cited articles
[1] Per Austrin, Ryan O’Donnell, Li-Yang Tan, and John Wright: New NP-hardness results for 3-coloring and 2-to-1 label cover. Technical report, 2012. Preliminary version in APPROX’12. [arXiv:1210.5648]
[2] 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 4th ISTCS, 1996. [doi:10.1006/inco.2000.3011]
[3] Irit Dinur, Elchanan Mossel, and Oded Regev: Conditional hardness for approximate coloring. SIAM J. Comput., 39(3):843–873, 2009. Preliminary version in STOC’06. [doi:10.1137/07068062X]
[4] Alan M. Frieze and Mark Jerrum: Improved approximation algorithms for MAX k-CUT and MAX BISECTION. Algorithmica, 18(1):67–81, 1997. Preliminary version in IPCO’95. [doi:10.1007/BF02523688]
[5] Venkatesan Guruswami: Inapproximability results for set splitting and satisfiability problems with no mixed clauses. Algorithmica, 38(3):451–469, 2004. Preliminary version in APPROX’00. [doi:10.1007/s00453-003-1072-z]
[6] Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, and Luca Trevisan: A tight characterization of NP with 3 query PCPs. In Proc. 39th FOCS, pp. 8–17. IEEE Comp. Soc. Press, 1998. [doi:10.1109/SFCS.1998.743424]
[7] Venkatesan Guruswami and Ali Kemal Sinop: Improved inapproximability results for maximum k-colorable subgraph. In Proc. 12th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’09), pp. 163–176. Springer, 2009. [doi:10.1007/978-3-642-03685-9_13]
[8] Johan HÃ¥stad: Some optimal inapproximability results. J. ACM, 48(4):798–859, 2001. Preliminary version in STOC’97. [doi:10.1145/502090.502098]
[9] Viggo Kann, Sanjeev Khanna, Jens Lagergren, and Alessandro Panconesi: On the hardness of approximating MAX k-CUT and its dual. Chicago J. Theor. Comput. Sci., 1997(2), 1997. CJTCS. Preliminary version in ISTCS’96.
[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] 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]
[12] Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz: Noise stability of functions with low influences: invariance and optimality. Ann. of Math., 171(1):295–341, 2010. Preliminary version in FOCS’05. [doi:10.4007/annals.2010.171.295]
[13] Ryan O’Donnell and Yi Wu: Conditional hardness for satisfiable 3-CSPs. In Proc. 41st STOC, pp. 493–502. ACM Press, 2009. [doi:10.1145/1536414.1536482]
[14] Christos H. Papadimitriou and Mihalis Yannakakis: Optimization, approximation, and complexity classes. J. Comput. System Sci., 43(3):425–440, 1991. Preliminary version in STOC’88. [doi:10.1016/0022-0000(91)90023-X]
[15] Erez Petrank: The hardness of approximation: Gap location. Comput. Complexity, 4(2):133–157, 1994. Preliminary version in ISTCS’93. [doi:10.1007/BF01202286]
[16] 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]
[17] Alistair Sinclair: Improved bounds for mixing rates of Markov chains and multicommodity flow. Combin. Probab. Comput., 1(4):351–370, 1992. Preliminary version in LATIN’92. [doi:10.1017/S0963548300000390]