{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,22]],"date-time":"2026-05-22T12:05:39Z","timestamp":1779451539012,"version":"3.53.1"},"reference-count":36,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2026,7]]},"DOI":"10.1016\/j.tcs.2026.116020","type":"journal-article","created":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T16:03:02Z","timestamp":1778169782000},"page":"116020","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["A fast algorithm for maximum satisfiability above half number of clauses"],"prefix":"10.1016","volume":"1078","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2742-5562","authenticated-orcid":false,"given":"Junqiang","family":"Peng","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1012-2373","authenticated-orcid":false,"given":"Mingyu","family":"Xiao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/j.tcs.2026.116020_bib0001","series-title":"Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, STOC 1971","first-page":"151","article-title":"The complexity of theorem-proving procedures","author":"Cook","year":"1971"},{"key":"10.1016\/j.tcs.2026.116020_bib0002","series-title":"Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1\u20133, 1978, San Diego, California, USA","first-page":"216","article-title":"The complexity of satisfiability problems","author":"Schaefer","year":"1978"},{"key":"10.1016\/j.tcs.2026.116020_bib0003","series-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"10.1016\/j.tcs.2026.116020_bib0004","article-title":"Handbook of Satisfiability - Second Edition","volume":"Vol. 336","year":"2021"},{"issue":"6","key":"10.1016\/j.tcs.2026.116020_bib0005","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1145\/3560469","article-title":"The silent (r)evolution of SAT","volume":"66","author":"Fichte","year":"2023","journal-title":"Commun. ACM"},{"issue":"2","key":"10.1016\/j.tcs.2026.116020_bib0006","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1006\/jcss.2000.1727","article-title":"On the complexity of k-SAT","volume":"62","author":"Impagliazzo","year":"2001","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1016\/j.tcs.2026.116020_bib0007","series-title":"Handbook of Satisfiability - Second Edition","first-page":"669","article-title":"Worst-case upper bounds","author":"Dantsin","year":"2021"},{"key":"10.1016\/j.tcs.2026.116020_bib0008","series-title":"Handbook of Satisfiability - Second Edition","first-page":"693","article-title":"Fixed-parameter tractability","author":"Samer","year":"2021"},{"key":"10.1016\/j.tcs.2026.116020_bib0009","series-title":"Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021","first-page":"3707","article-title":"An improved upper bound for SAT","author":"Chu","year":"2021"},{"key":"10.1016\/j.tcs.2026.116020_bib0010","doi-asserted-by":"crossref","DOI":"10.1016\/j.ic.2023.105085","article-title":"Further improvements for SAT in terms of formula length","volume":"294","author":"Peng","year":"2023","journal-title":"Inf. Comput."},{"key":"10.1016\/j.tcs.2026.116020_bib0011","series-title":"Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022","first-page":"1887","article-title":"An exact MaxSAT algorithm: further observations and further improvements","author":"Xiao","year":"2022"},{"key":"10.1016\/j.tcs.2026.116020_bib0012","series-title":"Proceedings of the AAAI Conference on Artificial Intelligence, AAAI 2023","first-page":"3898","article-title":"Improved algorithms for maximum satisfiability and its special cases","volume":"37","author":"Brilliantov","year":"2023"},{"key":"10.1016\/j.tcs.2026.116020_bib0013","series-title":"Thirty-Seventh AAAI Conference on Artificial Intelligence, AAAI 2023","first-page":"3915","article-title":"NuWLS: improving local search for (Weighted) partial MaxSAT by new weighting techniques","author":"Chu","year":"2023"},{"key":"10.1016\/j.tcs.2026.116020_bib0014","series-title":"Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023","first-page":"1979","article-title":"A new variable ordering for in-processing bounded variable elimination in SAT solvers","author":"Li","year":"2023"},{"issue":"2","key":"10.1016\/j.tcs.2026.116020_bib0015","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1006\/jagm.1998.0996","article-title":"Parameterizing above guaranteed values: MaxSat and MaxCut","volume":"31","author":"Mahajan","year":"1999","journal-title":"J. Algorithms"},{"key":"10.1016\/j.tcs.2026.116020_bib0016","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/j.tcs.2017.01.020","article-title":"Dealing with 4-variables by resolution: an improved MaxSAT algorithm","volume":"670","author":"Chen","year":"2017","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"10.1016\/j.tcs.2026.116020_bib0017","doi-asserted-by":"crossref","first-page":"638","DOI":"10.1007\/s00453-010-9428-7","article-title":"Solving MAX-r-SAT above a tight lower bound","volume":"61","author":"Alon","year":"2011","journal-title":"Algorithmica"},{"key":"10.1016\/j.tcs.2026.116020_bib0018","series-title":"Parameterized and Exact Computation - 6th International Symposium, IPEC 2011","first-page":"118","article-title":"Improved parameterized algorithms for above average constraint satisfaction","volume":"7112","author":"Kim","year":"2011"},{"issue":"1","key":"10.1016\/j.tcs.2026.116020_bib0019","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1007\/s00453-011-9550-1","article-title":"A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications","volume":"64","author":"Crowston","year":"2012","journal-title":"Algorithmica"},{"key":"10.1016\/j.tcs.2026.116020_bib0020","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/j.ic.2013.08.008","article-title":"A new bound for 3-satisfiable MaxSat and its algorithmic application","volume":"231","author":"Gutin","year":"2013","journal-title":"Inf. Comput."},{"issue":"3","key":"10.1016\/j.tcs.2026.116020_bib0021","doi-asserted-by":"crossref","first-page":"739","DOI":"10.1007\/s00453-012-9697-4","article-title":"Fixed-parameter tractability of satisfying beyond the number of variables","volume":"68","author":"Crowston","year":"2014","journal-title":"Algorithmica"},{"key":"10.1016\/j.tcs.2026.116020_bib0022","first-page":"7918","article-title":"Parameterization of (Partial) maximum satisfiability above matching in a variable-clause graph","author":"Alferov","year":"2024"},{"issue":"2","key":"10.1016\/j.tcs.2026.116020_bib0023","doi-asserted-by":"crossref","first-page":"15:1","DOI":"10.1145\/2566616","article-title":"Faster parameterized algorithms using linear programming","volume":"11","author":"Lokshtanov","year":"2014","journal-title":"ACM Trans. Algorithms"},{"key":"10.1016\/j.tcs.2026.116020_bib0024","series-title":"Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016","first-page":"1152","article-title":"Raising the bar for vertex cover: fixed-parameter tractability above a higher guarantee","author":"Garg","year":"2016"},{"issue":"1","key":"10.1016\/j.tcs.2026.116020_bib0025","doi-asserted-by":"crossref","first-page":"3:1","DOI":"10.1145\/2462896.2462899","article-title":"On multiway cut parameterized above lower bounds","volume":"5","author":"Cygan","year":"2013","journal-title":"ACM Trans. Comput. Theory"},{"issue":"2","key":"10.1016\/j.tcs.2026.116020_bib0026","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/j.jcss.2008.08.004","article-title":"Parameterizing above or below guaranteed values","volume":"75","author":"Mahajan","year":"2009","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1016\/j.tcs.2026.116020_bib0027","series-title":"IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2013, December 12\u201314, 2013, Guwahati, India","first-page":"43","article-title":"Polynomial kernels for lambda-extendible properties parameterized above the Poljak-Turzik bound","volume":"24","author":"Crowston","year":"2013"},{"issue":"4","key":"10.1016\/j.tcs.2026.116020_bib0028","doi-asserted-by":"crossref","first-page":"2326","DOI":"10.1137\/17M1148566","article-title":"Finding detours is fixed-parameter tractable","volume":"33","author":"Bez\u00e1kov\u00e1","year":"2019","journal-title":"SIAM J. Discret. Math."},{"issue":"3","key":"10.1016\/j.tcs.2026.116020_bib0029","doi-asserted-by":"crossref","first-page":"18:1","DOI":"10.1145\/3460956","article-title":"Multiplicative parameterization above a guarantee","volume":"13","author":"Fomin","year":"2021","journal-title":"ACM Trans. Comput. Theory"},{"key":"10.1016\/j.tcs.2026.116020_bib0030","series-title":"The Constraint Satisfaction Problem: Complexity and Approximability","first-page":"179","article-title":"Parameterized constraint satisfaction problems: a survey","volume":"7","author":"Gutin","year":"2017"},{"key":"10.1016\/j.tcs.2026.116020_bib0031","doi-asserted-by":"crossref","DOI":"10.1016\/j.cosrev.2025.100795","article-title":"A survey on graph problems parameterized above and below guaranteed values","volume":"58","author":"Gutin","year":"2025","journal-title":"Comput. Sci. Rev."},{"key":"10.1016\/j.tcs.2026.116020_bib0032","series-title":"Parameterized and Exact Computation, IPEC 2012","first-page":"37","article-title":"A new algorithm for parameterized MAX-SAT","author":"Bliznets","year":"2012"},{"issue":"17","key":"10.1016\/j.tcs.2026.116020_bib0033","doi-asserted-by":"crossref","first-page":"2147","DOI":"10.1016\/j.dam.2011.07.001","article-title":"Exact algorithms for dominating set","volume":"159","author":"van Rooij","year":"2011","journal-title":"Discret. Appl. Math."},{"key":"10.1016\/j.tcs.2026.116020_bib0034","series-title":"Exact Exponential Algorithms","author":"Fomin","year":"2010"},{"key":"10.1016\/j.tcs.2026.116020_bib0035","series-title":"ISAAC 1999","first-page":"247","article-title":"Upper bounds for MaxSat: further improved","author":"Bansal","year":"1999"},{"issue":"1","key":"10.1016\/j.tcs.2026.116020_bib0036","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/j.dam.2003.03.002","article-title":"Improved exact algorithms for MAX-SAT","volume":"142","author":"Chen","year":"2004","journal-title":"Discret. Appl. Math."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397526002707?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397526002707?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,5,22]],"date-time":"2026-05-22T11:13:39Z","timestamp":1779448419000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397526002707"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7]]},"references-count":36,"alternative-id":["S0304397526002707"],"URL":"https:\/\/doi.org\/10.1016\/j.tcs.2026.116020","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2026,7]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"A fast algorithm for maximum satisfiability above half number of clauses","name":"articletitle","label":"Article Title"},{"value":"Theoretical Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.tcs.2026.116020","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.","name":"copyright","label":"Copyright"}],"article-number":"116020"}}