{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T04:27:22Z","timestamp":1778732842662,"version":"3.51.4"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2019,5,17]],"date-time":"2019-05-17T00:00:00Z","timestamp":1558051200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,5,17]],"date-time":"2019-05-17T00:00:00Z","timestamp":1558051200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61502054"],"award-info":[{"award-number":["61502054"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61672536"],"award-info":[{"award-number":["61672536"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61702557"],"award-info":[{"award-number":["61702557"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61420106009"],"award-info":[{"award-number":["61420106009"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004735","name":"Natural Science Foundation of Hunan Province","doi-asserted-by":"publisher","award":["2017JJ3333"],"award-info":[{"award-number":["2017JJ3333"]}],"id":[{"id":"10.13039\/501100004735","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Scientific Research Fund of Hunan Provincial Education Department","award":["17C0047"],"award-info":[{"award-number":["17C0047"]}]},{"DOI":"10.13039\/501100002858","name":"China Postdoctoral Science Foundation","doi-asserted-by":"publisher","award":["2017M612584"],"award-info":[{"award-number":["2017M612584"]}],"id":[{"id":"10.13039\/501100002858","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100010021","name":"Postdoctoral Science Foundation of Central South University","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100010021","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61872048"],"award-info":[{"award-number":["61872048"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2021,10]]},"DOI":"10.1007\/s10878-019-00421-1","type":"journal-article","created":{"date-parts":[[2019,5,17]],"date-time":"2019-05-17T06:28:15Z","timestamp":1558074495000},"page":"524-542","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["An improved algorithm for the $$(n, 3)$$-MaxSAT problem: asking branchings to satisfy the clauses"],"prefix":"10.1007","volume":"42","author":[{"given":"Chao","family":"Xu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenjun","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianxin","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7731-6818","authenticated-orcid":false,"given":"Yongjie","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,5,17]]},"reference":[{"issue":"4\u20135","key":"421_CR1","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s10732-006-7234-9","volume":"12","author":"J Argelich","year":"2006","unstructured":"Argelich J, Many\u00e0 F (2006) Exact Max-SAT solvers for over-constrained problems. J Heuristics 12(4\u20135):375\u2013392","journal-title":"J Heuristics"},{"issue":"3","key":"421_CR2","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B Aspvall","year":"1979","unstructured":"Aspvall B, Plass MF, Tarjan RE (1979) A linear-time algorithm for testing the truth of certain quantified boolean formulas. Inf Process Lett 8(3):121\u2013123","journal-title":"Inf Process Lett"},{"key":"421_CR3","doi-asserted-by":"crossref","unstructured":"Bansal N, Raman V (1999) Upper bounds for MaxSAT: further improved. In: ISAAC, pp 247\u2013258","DOI":"10.1007\/3-540-46632-0_26"},{"key":"421_CR4","unstructured":"Berg J, Hyttinen A, J\u00e4rvisalo M (2015) Applications of MaxSAT in data analysis. In: Pragmatics of SAT workshop"},{"key":"421_CR5","doi-asserted-by":"crossref","unstructured":"Bliznets I, Golovnev A (2012) A new algorithm for parameterized MAX-SAT. In: IPEC, pp 37\u201348","DOI":"10.1007\/978-3-642-33293-7_6"},{"issue":"1","key":"421_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10958-012-1101-z","volume":"188","author":"IA Bliznets","year":"2013","unstructured":"Bliznets IA (2013) A new upper bound for $$(n, 3)$$-MAX-SAT. J Math Sci 188(1):1\u20136","journal-title":"J Math Sci"},{"issue":"8\u20139","key":"421_CR7","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1016\/j.artint.2007.03.001","volume":"171","author":"ML Bonet","year":"2007","unstructured":"Bonet ML, Levy J, Many\u00e0 F (2007) Resolution for Max-SAT. Artif Intell 171(8\u20139):606\u2013618","journal-title":"Artif Intell"},{"key":"421_CR8","doi-asserted-by":"crossref","unstructured":"Calabro C, Impagliazzo R, Paturi R (2006) A duality between clause width and clause density for SAT. In: CCC, pp 252\u2013260","DOI":"10.1109\/CCC.2006.6"},{"issue":"1\u20133","key":"421_CR9","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/j.dam.2003.03.002","volume":"142","author":"J Chen","year":"2004","unstructured":"Chen J, Kanj IA (2004) Improved exact algorithms for Max-Sat. Discrete Appl Math 142(1\u20133):17\u201327","journal-title":"Discrete Appl Math"},{"issue":"40\u201342","key":"421_CR10","doi-asserted-by":"publisher","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J Chen","year":"2010","unstructured":"Chen J, Kanj IA, Xia G (2010) Improved upper bounds for vertex cover. Theor Comput Sci 411(40\u201342):3736\u20133756","journal-title":"Theor Comput Sci"},{"key":"421_CR11","doi-asserted-by":"crossref","unstructured":"Cook SA (1971) The complexity of theorem-proving procedures. In: STOC, pp 151\u2013158","DOI":"10.1145\/800157.805047"},{"key":"421_CR12","first-page":"467","volume-title":"Lower bounds based on the exponential-time hypothesis","author":"M Cygan","year":"2015","unstructured":"Cygan M, Fomin FV, Kowalik L, Lokshtanov D, Marx D, Pilipczuk M, Pilipczuk M, Saurabh S (2015) Lower bounds based on the exponential-time hypothesis. Springer, Berlin, pp 467\u2013521"},{"key":"421_CR13","series-title":"Texts in theoretical computer science An EATCS series","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact exponential algorithms, chapter 2","author":"FV Fomin","year":"2010","unstructured":"Fomin FV, Kratsch D (2010) Exact exponential algorithms, chapter 2. Texts in theoretical computer science An EATCS series. Springer, Berlin, pp 13\u201330"},{"key":"421_CR14","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"M Garey","year":"1979","unstructured":"Garey M, Johnson D (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman, New York"},{"issue":"4","key":"421_CR15","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1137\/S0895480192243516","volume":"7","author":"MX Goemans","year":"1994","unstructured":"Goemans MX, Williamson DP (1994) New 3\/4-approximation algorithms for the maximum satisfiability problem. SIAM J Discrete Math 7(4):656\u2013666","journal-title":"SIAM J Discrete Math"},{"issue":"6","key":"421_CR16","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J ACM 42(6):1115\u20131145","journal-title":"J ACM"},{"issue":"3","key":"421_CR17","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1109\/69.334864","volume":"6","author":"J Gu","year":"1994","unstructured":"Gu J (1994) Global optimization for satisfiability (SAT) problem. IEEE Trans Knowl Data Eng 6(3):361\u2013381","journal-title":"IEEE Trans Knowl Data Eng"},{"issue":"4","key":"421_CR18","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1023\/A:1006340920104","volume":"24","author":"EA Hirsch","year":"2000","unstructured":"Hirsch EA (2000) New worst-case upper bounds for SAT. J Autom Reason 24(4):397\u2013420","journal-title":"J Autom Reason"},{"issue":"1","key":"421_CR19","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s10472-005-0421-9","volume":"43","author":"EA Hirsch","year":"2005","unstructured":"Hirsch EA, Kojevnikov A (2005) Unitwalk: a new SAT solver that uses local search guided by unit clause elimination. Ann Math Artif Intell 43(1):91\u2013111","journal-title":"Ann Math Artif Intell"},{"key":"421_CR20","volume-title":"Approximation algorithms for NP-hard problems","author":"D Hochbaum","year":"1997","unstructured":"Hochbaum D (1997) Approximation algorithms for NP-hard problems. PWS Publishing Company, Boston"},{"key":"421_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.artint.2016.09.006","volume":"243","author":"F Hutter","year":"2017","unstructured":"Hutter F, Lindauer M, Balint A, Bayless S, Hoos H, Leyton-Brown K (2017) The configurable SAT solver challenge (CSSC). Artif Intell 243:1\u201325","journal-title":"Artif Intell"},{"issue":"2","key":"421_CR22","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo R, Paturi R (2001) On the complexity of $$k$$-SAT. J Comput Syst Sci 62(2):367\u2013375","journal-title":"J Comput Syst Sci"},{"key":"421_CR23","unstructured":"Karloff HJ, Zwick U (1997) A 7\/8-approximation algorithm for MAX 3SAT? In: FOCS, pp 406\u2013415"},{"key":"421_CR24","doi-asserted-by":"crossref","unstructured":"Kulikov AS (2005) Automated generation of simplification rules for SAT and MAXSAT. In: SAT, pp 430\u2013436","DOI":"10.1007\/11499107_35"},{"key":"421_CR25","doi-asserted-by":"crossref","unstructured":"Li W, Xu C, Wang J, Yang Y (2017) An improved branching algorithm for $$(n, 3)$$-MaxSAT based on refined observations. In: COCOA, pp 94\u2013108","DOI":"10.1007\/978-3-319-71147-8_7"},{"key":"421_CR26","unstructured":"Lokshtanov D (2009) New methods in parameterized algorithms and complexity. Ph.D. thesis, University of Bergen"},{"key":"421_CR27","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.artint.2016.11.001","volume":"243","author":"C Luo","year":"2017","unstructured":"Luo C, Cai S, Su K, Huang W (2017) CCEHC: an efficient local search algorithm for weighted partial maximum satisfiability. Artif Intell 243:26\u201344","journal-title":"Artif Intell"},{"issue":"1","key":"421_CR28","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1006\/jagm.2000.1075","volume":"36","author":"R Niedermeier","year":"2000","unstructured":"Niedermeier R, Rossmanith P (2000) New upper bounds for maximum satisfiability. J Algorithms 36(1):63\u201388","journal-title":"J Algorithms"},{"key":"421_CR29","doi-asserted-by":"crossref","unstructured":"Patrascu M, Williams R (2010) On the possibility of faster SAT algorithms. In: SODA, pp 1065\u20131075","DOI":"10.1137\/1.9781611973075.86"},{"issue":"3","key":"421_CR30","doi-asserted-by":"publisher","first-page":"1029","DOI":"10.1137\/15M1053369","volume":"46","author":"M Poloczek","year":"2017","unstructured":"Poloczek M, Schnitger G, Williamson DP, van Zuylen A (2017) Greedy algorithms for the maximum satisfiability problem: simple algorithms and inapproximability bounds. SIAM J Comput 46(3):1029\u20131061","journal-title":"SIAM J Comput"},{"issue":"1","key":"421_CR31","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 SS (1998) A simplified NP-complete MAXSAT problem. Inf Process Lett 65(1):1\u20136","journal-title":"Inf Process Lett"},{"key":"421_CR32","doi-asserted-by":"crossref","unstructured":"Saikko P, Malone B, J\u00e4rvisalo M (2015) MaxSAT-based cutting planes for learning graphical models. In: CPAIOR, pp 347\u2013356","DOI":"10.1007\/978-3-319-18008-3_24"},{"issue":"1\u20132","key":"421_CR33","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0004-3702(95)00045-3","volume":"81","author":"B Selman","year":"1996","unstructured":"Selman B, Mitchell DG, Levesque HJ (1996) Generating hard satisfiability problems. Artif Intell 81(1\u20132):17\u201329","journal-title":"Artif Intell"},{"issue":"4","key":"421_CR34","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/s10472-005-7036-z","volume":"44","author":"H Shen","year":"2005","unstructured":"Shen H, Zhang H (2005) Improving exact algorithms for MAX-2-SAT. Ann Math Artif Intell 44(4):419\u2013436","journal-title":"Ann Math Artif Intell"},{"key":"421_CR35","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/j.dam.2014.07.009","volume":"199","author":"M Xiao","year":"2016","unstructured":"Xiao M, Nagamochi H (2016) An exact algorithm for maximum independent set in degree-5 graphs. Discrete Appl Math 199:137\u2013155","journal-title":"Discrete Appl Math"},{"key":"421_CR36","unstructured":"Xu C, Chen J, Wang J (2016) Resolution and linear CNF formulas: improved $$(n, 3)$$-MaxSAT algorithms. Theor Comput Sci (to appear)"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-019-00421-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-019-00421-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-019-00421-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,30]],"date-time":"2021-10-30T06:31:28Z","timestamp":1635575488000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-019-00421-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,17]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["421"],"URL":"https:\/\/doi.org\/10.1007\/s10878-019-00421-1","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,17]]},"assertion":[{"value":"17 May 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}