{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,16]],"date-time":"2026-09-16T18:04:03Z","timestamp":1789581843225,"version":"build-2803163510"},"publisher-location":"Singapore","reference-count":22,"publisher":"Springer Nature Singapore","isbn-type":[{"value":"9789819683116","type":"print"},{"value":"9789819683123","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-981-96-8312-3_8","type":"book-chapter","created":{"date-parts":[[2025,6,29]],"date-time":"2025-06-29T06:15:05Z","timestamp":1751177705000},"page":"103-117","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["From MAXCUT to\u00a0MAXNAESAT: Elegant Proofs and\u00a0Algorithmic Advances"],"prefix":"10.1007","author":[{"given":"Sangram K.","family":"Jena","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"K.","family":"Subramani","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,6,30]]},"reference":[{"issue":"1\u20132","key":"8_CR1","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"P Alimonti","year":"2000","unstructured":"Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. Theoret. Comput. Sci. 237(1\u20132), 123\u2013134 (2000)","journal-title":"Theoret. Comput. Sci."},{"key":"8_CR2","doi-asserted-by":"crossref","unstructured":"Berman, P., Karpinski, M.: On some tighter inapproximability results. In: International Colloquium on Automata, Languages, and Programming, pp. 200\u2013209 (1999)","DOI":"10.1007\/3-540-48523-6_17"},{"issue":"1","key":"8_CR3","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1137\/23M1591578","volume":"39","author":"J Brakensiek","year":"2025","unstructured":"Brakensiek, J., Huang, N., Potechin, A., Zwick, U.: On the mysteries of MAX NAE-SAT. SIAM J. Discret. Math. 39(1), 267\u2013313 (2025)","journal-title":"SIAM J. Discret. Math."},{"issue":"4","key":"8_CR4","doi-asserted-by":"publisher","first-page":"940","DOI":"10.1007\/s00453-014-9883-7","volume":"72","author":"K Edwards","year":"2015","unstructured":"Edwards, K., McDermid, E.: A general reduction theorem with applications to pathwidth and the complexity of MAX 2-CSP. Algorithmica 72(4), 940\u2013968 (2015)","journal-title":"Algorithmica"},{"key":"8_CR5","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series. Springer (2010)","DOI":"10.1007\/978-3-642-16533-7"},{"key":"8_CR6","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman Company, San Francisco (1979)"},{"key":"8_CR7","doi-asserted-by":"crossref","unstructured":"Gaspers, S., Sorkin, G.B.: Separate, measure and conquer: faster polynomial-space algorithms for MAX 2-CSP and counting dominating sets. ACM Trans. Algorithms (TALG) 13(4), 1\u201336, (2017)","DOI":"10.1145\/3111499"},{"issue":"6","key":"8_CR8","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM (JACM) 42(6), 1115\u20131145 (1995)","journal-title":"J. ACM (JACM)"},{"issue":"4","key":"8_CR9","doi-asserted-by":"publisher","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 (JACM) 48(4), 798\u2013859 (2001)","journal-title":"J. ACM (JACM)"},{"key":"8_CR10","doi-asserted-by":"crossref","unstructured":"Kann, V., Lagergren, J., Panconesi, A.: Approximability of Maximum Splitting of k-sets and some other APX-complete Problems. Citeseer (1995)","DOI":"10.1016\/0020-0190(96)00046-4"},{"issue":"1","key":"8_CR11","doi-asserted-by":"publisher","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 Jo. Comput. 37(1), 319\u2013357 (2007)","journal-title":"SIAM Jo. Comput."},{"key":"8_CR12","unstructured":"Lee, A., Xu, B.: Classifying approximation algorithms: understanding the APX complexity class. arXiv preprint arXiv:2111.01551 (2021)"},{"key":"8_CR13","doi-asserted-by":"crossref","unstructured":"Li, W., Xu, C., Wang, J., Yang, Y.: An improved branching algorithm for (n, 3)-maxsat based on refined observations. In: International Conference on Combinatorial Optimization and Applications, pp. 94\u2013108 (2017)","DOI":"10.1007\/978-3-319-71147-8_7"},{"key":"8_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1007\/978-3-642-39071-5_29","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2013","author":"N Misra","year":"2013","unstructured":"Misra, N., Ordyniak, S., Raman, V., Szeider, S.: Upper and Lower Bounds for Weak Backdoor Set Detection. In: J\u00e4rvisalo, M., Van Gelder, A. (eds.) SAT 2013. LNCS, vol. 7962, pp. 394\u2013402. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-39071-5_29"},{"key":"8_CR15","volume-title":"Papadimitriou","author":"H Christos","year":"1994","unstructured":"Christos, H.: Papadimitriou. Addison-Wesley, Computational complexity (1994)"},{"issue":"3","key":"8_CR16","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"CH Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci."},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"Porschen, S., Randerath, B., Speckenmeyer, E.: Linear time algorithms for some not-all-equal satisfiability problems. In: SAT, pp. 172\u2013187 (2003)","DOI":"10.1007\/978-3-540-24605-3_14"},{"issue":"1","key":"8_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0020-0190(97)00223-8","volume":"65","author":"V Raman","year":"1998","unstructured":"Raman, V., Ravikumar, B., Rao, S.S.: A simplified np-complete MAXSAT problem. Inf. Process. Lett. 65(1), 1\u20136 (1998)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"8_CR19","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1080\/00207161003631893","volume":"88","author":"K Subramani","year":"2011","unstructured":"Subramani, K., Gu, X.: Absorbing random walks and the NAE2SAT problem. Int. J. Comput. Math. 88(3), 452\u2013467 (2011)","journal-title":"Int. J. Comput. Math."},{"key":"8_CR20","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.tcs.2016.05.040","volume":"657","author":"A Xian","year":"2017","unstructured":"Xian, A., Zhu, K., Zhu, D., Lianrong, P., Liu, H.: Approximating Max NAE-k-SAT by anonymous local search. Theoret. Comput. Sci. 657, 54\u201363 (2017)","journal-title":"Theoret. Comput. Sci."},{"issue":"1\u20133","key":"8_CR21","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/j.dam.2002.07.001","volume":"142","author":"J Zhang","year":"2004","unstructured":"Zhang, J., Ye, Y., Han, Q.: Improved approximations for max set splitting and max NAE SAT. Discret. Appl. Math. 142(1\u20133), 133\u2013149 (2004)","journal-title":"Discret. Appl. Math."},{"key":"8_CR22","first-page":"201","volume":"98","author":"U Zwick","year":"1998","unstructured":"Zwick, U.: Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint. SODA 98, 201\u2013210 (1998)","journal-title":"SODA"}],"container-title":["Lecture Notes in Computer Science","Frontiers of Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-96-8312-3_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,9,16]],"date-time":"2026-09-16T17:38:43Z","timestamp":1789580323000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-96-8312-3_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9789819683116","9789819683123"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-981-96-8312-3_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"30 June 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IJTCS-FAW","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Frontiers in Algorithmics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Paris","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 June 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 July 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"faw2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ijtcs-faw.github.io\/2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}