{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:24Z","timestamp":1740109404496,"version":"3.37.3"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,6,25]],"date-time":"2015-06-25T00:00:00Z","timestamp":1435190400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2016,7]]},"DOI":"10.1007\/s00224-015-9638-0","type":"journal-article","created":{"date-parts":[[2015,6,24]],"date-time":"2015-06-24T06:33:28Z","timestamp":1435127608000},"page":"76-98","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Complexity of Approximating CSP with Balance \/ Hard Constraints"],"prefix":"10.1007","volume":"59","author":[{"given":"Venkatesan","family":"Guruswami","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1454-7587","authenticated-orcid":false,"given":"Euiwoong","family":"Lee","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,25]]},"reference":[{"key":"9638_CR1","doi-asserted-by":"crossref","unstructured":"Agarwal, A., Charikar, M., Makarychev, K., Yury, M.: O ( log n ) $(\\sqrt {\\log n})$ -approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, STOC \u201905, pp 573\u2013581 (2005)","DOI":"10.1145\/1060590.1060675"},{"key":"9638_CR2","doi-asserted-by":"crossref","unstructured":"Austrin, P., Benabbas, S., Georgiou, K.: Better balance by being biased: a 0.8776-approximation for max bisection. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201913, pp 373\u2013387 (2013)","DOI":"10.1137\/1.9781611973105.21"},{"key":"9638_CR3","doi-asserted-by":"crossref","unstructured":"Austrin, P., Khot, S., Safra, M.: Inapproximability of vertex cover and independent set in bounded degree graphs. In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC \u201909, pp 74\u201380 (2009)","DOI":"10.1109\/CCC.2009.38"},{"key":"9638_CR4","doi-asserted-by":"crossref","unstructured":"Avidor, A., Berkovitch, I., Zwick, U.: Improved approximation algorithms for Max NAE-SAT and Max SAT. In: Erlebach, T., Persinao, G. (eds.) Approximation and Online Algorithms of Lecture Notes in Computer Science, vol. 3879, pp 27\u201340 (2006)","DOI":"10.1007\/11671411_3"},{"key":"9638_CR5","doi-asserted-by":"crossref","unstructured":"Bansal, N., Khot, S.: Inapproximability of hypergraph vertex cover and applications to scheduling problems. In: Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP \u201910, pp 250\u2013261 (2010)","DOI":"10.1007\/978-3-642-14165-2_22"},{"issue":"9","key":"9638_CR6","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1145\/1810891.1810914","volume":"53","author":"AA Bulatov","year":"2010","unstructured":"Bulatov, A.A., Marx, D.: Constraint satisfaction problems and global cardinality constraints. Commun. ACM 53(9), 99\u2013106 (2010)","journal-title":"Commun. ACM"},{"key":"9638_CR7","doi-asserted-by":"crossref","unstructured":"Charikar, M., Makarychev, K., Makarychev, Y.: Near-optimal algorithms for maximum constraint satisfaction problems. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201907, pp 62\u201368 (2007)","DOI":"10.1145\/1132516.1132547"},{"key":"9638_CR8","doi-asserted-by":"crossref","unstructured":"Creignou, N., Schnoor, H., Schnoor, I.: Nonuniform boolean constraint satisfaction problems with cardinality constraint. ACM Trans. Comput. Log. 11(4) (2010)","DOI":"10.1145\/1805950.1805954"},{"issue":"4","key":"9638_CR9","doi-asserted-by":"crossref","first-page":"15:1","DOI":"10.1145\/2540090","volume":"5","author":"V Dalmau","year":"2013","unstructured":"Dalmau, V., Krokhin, A.: Robust satisfiability for CSPs: hardness and algorithmic results. ACM Transactions on Computation Theory 5(4), 15:1\u201315:25 (2013)","journal-title":"ACM Transactions on Computation Theory"},{"key":"9638_CR10","doi-asserted-by":"crossref","unstructured":"Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover Annals of Mathematics, pp 439\u2013485 (2005)","DOI":"10.4007\/annals.2005.162.439"},{"issue":"5","key":"9638_CR11","doi-asserted-by":"crossref","first-page":"1129","DOI":"10.1137\/S0097539704443057","volume":"34","author":"I Dinur","year":"2005","unstructured":"Dinur, I., Guruswami, V., Khot, S., Regev, O.: A new multilayered PCP and the hardness of hypergraph vertex cover. SIAM J. Comput. 34(5), 1129\u20131146 (2005)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9638_CR12","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/PL00009191","volume":"20","author":"G Even","year":"1998","unstructured":"Even, G., Naor, J.S., Schieber, B., Sudan, M.: Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica 20(2), 151\u2013174 (1998)","journal-title":"Algorithmica"},{"key":"9638_CR13","doi-asserted-by":"crossref","unstructured":"Feige, U., Langberg, M.: The RPR2 rounding technique for semidefinite programs. In: Proceedings of the 28th International Colloquium on Automata, Languages and Programming, ICALP \u201901, pp 213\u2013224 (2001)","DOI":"10.1007\/3-540-48224-5_18"},{"key":"9638_CR14","doi-asserted-by":"crossref","unstructured":"Frieze, A., Jerrum, M.: Improved approximation algorithms for Max k-Cut and Max Bisection. In: Proceedings of the 4th Conference on Integer Programming and Combinatorial Optimization, IPCO \u201995, pp 1\u201313 (1995)","DOI":"10.1007\/3-540-59408-6_37"},{"issue":"4","key":"9638_CR15","doi-asserted-by":"crossref","first-page":"656","DOI":"10.1137\/S0895480192243516","volume":"7","author":"M Goemans","year":"1994","unstructured":"Goemans, M., Williamson, D.: New 3 4 $\\frac {3}{4}$ -approximation algorithms for the maximum satisfiability problem. SIAM J. Discret. Math. 7(4), 656\u2013666 (1994)","journal-title":"SIAM J. Discret. Math."},{"issue":"6","key":"9638_CR16","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M Goemans","year":"1995","unstructured":"Goemans, M., Williamson, D.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6), 1115\u20131145 (1995)","journal-title":"J. ACM"},{"key":"9638_CR17","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Lee, E.: Complexity of approximating CSP with balance \/ hard constraints. In: Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, ITCS \u201914 (2014)","DOI":"10.1145\/2554797.2554837"},{"key":"9638_CR18","unstructured":"Guruswami, V., Makarychev, Y., Raghavendra, P., Steurer, D., Zhou, Y.: Finding almost-perfect graph bisections. In: Proceedings of the 2nd Symposium on Innovations in Computer Science, ICS \u201911, pp 321\u2013337 (2011)"},{"key":"9638_CR19","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Manokaran, R., Raghavendra, P.: Beating the random ordering is hard: inapproximability of maximum acyclic subgraph. In: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS \u201908, pp 573\u2013582 (2008)","DOI":"10.1109\/FOCS.2008.51"},{"issue":"1","key":"9638_CR20","doi-asserted-by":"crossref","first-page":"239","DOI":"10.4086\/toc.2012.v008a011","volume":"8","author":"V Guruswami","year":"2012","unstructured":"Guruswami, V., Zhou, Y.: Tight bounds on the approximability of almost-satisfiable horn SAT and exact hitting set. Theory of Computing 8(1), 239\u2013267 (2012)","journal-title":"Theory of Computing"},{"key":"9638_CR21","doi-asserted-by":"crossref","unstructured":"Halperin, E., Zwick, U.: A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems. In: Proceedings of the 8th conference on Integer Programming and Combinatorial Optimization, IPCO \u201901, pp 210\u2013225 (2001)","DOI":"10.1007\/3-540-45535-3_17"},{"issue":"4","key":"9638_CR22","doi-asserted-by":"crossref","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. J. ACM 48(4), 798\u2013859 (2001)","journal-title":"J. ACM"},{"key":"9638_CR23","doi-asserted-by":"crossref","unstructured":"Holmerin, J., Khot, S.: A new PCP outer verifier with applications to homogeneous linear equations and Max-bisection. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, STOC \u201904, pp 11\u201320 (2004)","DOI":"10.1145\/1007352.1007362"},{"issue":"6","key":"9638_CR24","doi-asserted-by":"crossref","first-page":"1863","DOI":"10.1137\/S0097539799349948","volume":"30","author":"S Khanna","year":"2001","unstructured":"Khanna, S., Sudan, M., Trevisan, L., Williamson, D.: The approximability of constraint satisfaction problems. SIAM J. Comput. 30(6), 1863\u20131920 (2001)","journal-title":"SIAM J. Comput."},{"key":"9638_CR25","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, STOC \u201902, pp 767\u2013775 (2002)","DOI":"10.1145\/509907.510017"},{"issue":"1","key":"9638_CR26","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1137\/S0097539705447372","volume":"37","author":"S Khot","year":"2007","unstructured":"Khot, S., Kindler, G., Mossel, E., O\u2019Donnell, R.: Optimal inapproximability results for max-cut and other 2-variable CSPs. SIAM J. Comput. 37(1), 319\u2013357 (2007)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9638_CR27","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2 \u2212 \u03b5. J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"9638_CR28","doi-asserted-by":"crossref","unstructured":"Lewin, M., Livnat, D., Zwick, U.: Improved rounding techniques for the Max 2-SAT and Max Di-Cut problems. In: Proceedings of the 9th Conference on Integer Programming and Combinatorial Optimization, IPCO \u201902, pp 67\u201382 (2002)","DOI":"10.1007\/3-540-47867-1_6"},{"key":"9638_CR29","doi-asserted-by":"crossref","first-page":"295","DOI":"10.4007\/annals.2010.171.295","volume":"171","author":"E Mossel","year":"2010","unstructured":"Mossel, E., O\u2019Donnell, R., Oleszkiewicz, K.: Noise stability of functions with low influences: invariance and optimality. Ann. Math. 171, 295\u2013341 (2010)","journal-title":"Ann. Math."},{"issue":"3","key":"9638_CR30","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C Papadimitriou","year":"1991","unstructured":"Papadimitriou, C., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci."},{"key":"9638_CR31","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Tan, N.: Approximating CSPs with global cardinality constraints using SDP hierarchies. In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201912, pp 373\u2013387 (2012)","DOI":"10.1137\/1.9781611973099.33"},{"key":"9638_CR32","doi-asserted-by":"crossref","unstructured":"Schaefer, T.: The complexity of satisfiability problems. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing, STOC \u201978, pp 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"9638_CR33","doi-asserted-by":"crossref","unstructured":"Svensson, O.: Hardness of vertex deletion and project scheduling. In: Gupta, A., Jansen, K., Rolim, J., Servedio, R. (eds.) Approximation, Randomization, and Combinatorial Optimization, Algorithms and Techniques of Lecture Notes in Computer Science, vol. 7408, pp 301\u2013312 (2012)","DOI":"10.1007\/978-3-642-32512-0_26"},{"issue":"1","key":"9638_CR34","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/PL00011415","volume":"90","author":"Y Yinyu","year":"2001","unstructured":"Yinyu, Y.: A .699-approximation algorithm for Max-Bisection. Math. Program. 90(1), 101\u2013111 (2001)","journal-title":"Math. Program."},{"key":"9638_CR35","doi-asserted-by":"crossref","unstructured":"Zwick, U.: Finding almost-satisfying assignments. In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC \u201998, pp 551\u2013560 (1998)","DOI":"10.1145\/276698.276869"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-015-9638-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-015-9638-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-015-9638-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,11]],"date-time":"2023-08-11T19:05:36Z","timestamp":1691780736000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-015-9638-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,25]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,7]]}},"alternative-id":["9638"],"URL":"https:\/\/doi.org\/10.1007\/s00224-015-9638-0","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2015,6,25]]}}}