{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:08Z","timestamp":1740122408647,"version":"3.37.3"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,2,27]],"date-time":"2018-02-27T00:00:00Z","timestamp":1519689600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11626039","61702019"],"award-info":[{"award-number":["11626039","61702019"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Beijing committee project of talented youth","award":["2016000020124G028"],"award-info":[{"award-number":["2016000020124G028"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2018,5]]},"DOI":"10.1007\/s10878-018-0267-9","type":"journal-article","created":{"date-parts":[[2018,2,26]],"date-time":"2018-02-26T21:16:03Z","timestamp":1519679763000},"page":"1286-1299","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the lower bounds of random Max 3 and 4-SAT"],"prefix":"10.1007","volume":"35","author":[{"given":"Guangyan","family":"Zhou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zongsheng","family":"Gao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,2,27]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Achlioptas D, Moore C (2002) The asymptotic order of the random $$k$$ k -SAT threshold. In: Proceedings of 43rd annual symposium on foundations of computer science, pp 126\u2013127","key":"267_CR1","DOI":"10.1109\/SFCS.2002.1182003"},{"issue":"4","key":"267_CR2","doi-asserted-by":"publisher","first-page":"947","DOI":"10.1090\/S0894-0347-04-00464-3","volume":"17","author":"D Achlioptas","year":"2004","unstructured":"Achlioptas D, Peres Y (2004) The threshold for random $$k$$ k -SAT is $$2^k\\log 2-O(k)$$ 2 k log 2 - O ( k ) . J Am Math Soc 17(4):947\u2013973","journal-title":"J Am Math Soc"},{"issue":"2","key":"267_CR3","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1145\/1219092.1219098","volume":"54","author":"D Achlioptas","year":"2007","unstructured":"Achlioptas D, Naor A, Peres Y (2007) On the maximum satisfiability of random formulas. J Assoc Comput Mach 54(2):10","journal-title":"J Assoc Comput Mach"},{"issue":"4","key":"267_CR4","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1023\/A:1009725216438","volume":"2","author":"B Borchers","year":"1998","unstructured":"Borchers B, Furman J (1998) A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems. J Comb Optim 2(4):299\u2013306","journal-title":"J Comb Optim"},{"unstructured":"Broder AZ, Frieze AM, Upfal E (1993) On the satisfiability and maximum satisfiability of random 3-CNF formulas. In: Proceedings of 4th annual ACM-SIAM symposium on discrete algorithms, pp 322\u2013330","key":"267_CR5"},{"unstructured":"Coppersmith D, Gamarnik D, Hajiaghayi MT, Sorkin GB (2003) Random MAX 2-SAT and MAX CUT. In: 14th annual ACM-SIAM symposium on discrete algorithms (Baltimore, MD, 2003). ACM, New York","key":"267_CR6"},{"key":"267_CR7","volume-title":"Asymptotic methods in analysis","author":"NG Bruijn de","year":"1981","unstructured":"de Bruijn NG (1981) Asymptotic methods in analysis, 3rd edn. Dover Publications Inc., New York","edition":"3"},{"unstructured":"de la Vega WF, Karpinski M (2002) 9\/8-approximation algorithm for random MAX 3-SAT. Technical Report TR02-070. Electronic Colloquium on Computational Complexity","key":"267_CR8"},{"key":"267_CR9","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1137\/S0895480192243516","volume":"7","author":"M Goemans","year":"1994","unstructured":"Goemans M, Williamson D (1994) New 3\/4-approximation algorithms for the maximum satisfiability problem. SIAM J Discrete Math 7:656\u2013666","journal-title":"SIAM J Discrete Math"},{"issue":"4","key":"267_CR10","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"H\u00e5stad J (2001) Some optimal inapproximability results. J ACM 48(4):798\u2013859","journal-title":"J ACM"},{"doi-asserted-by":"crossref","unstructured":"Hirsch EA (2000) A new algorithm for MAX 2-SAT, STACS 2000, LNCS 1770, pp 65\u201373","key":"267_CR11","DOI":"10.1007\/3-540-46541-3_5"},{"key":"267_CR12","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1002\/rsa.20104","volume":"28","author":"AC Kaporis","year":"2006","unstructured":"Kaporis AC, Kirousis LM, Lalas EG (2006) The probabilistic analysis of a greedy satisfiability algorithm. Random Struct Algorithms 28:444\u2013480","journal-title":"Random Struct Algorithms"},{"issue":"9","key":"267_CR13","doi-asserted-by":"publisher","first-page":"092101","DOI":"10.1007\/s11432-016-5526-8","volume":"59","author":"J Liu","year":"2016","unstructured":"Liu J, Xu K (2016) A novel weighting scheme for random $$k$$ k -SAT. Sci China Inf Sci 59(9):092101. https:\/\/doi.org\/10.1007\/s11432-016-5526-8","journal-title":"Sci China Inf Sci"},{"issue":"3","key":"267_CR14","first-page":"287","volume":"17","author":"FYu Vorob\u2019ev","year":"2007","unstructured":"Vorob\u2019ev FYu (2007) A lower bound for the 4-satisfiability threshold. Discrete Math Appl 17(3):287\u2013294","journal-title":"Discrete Math Appl"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-018-0267-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0267-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0267-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,11]],"date-time":"2019-10-11T18:22:23Z","timestamp":1570818143000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-018-0267-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,27]]},"references-count":14,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,5]]}},"alternative-id":["267"],"URL":"https:\/\/doi.org\/10.1007\/s10878-018-0267-9","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2018,2,27]]},"assertion":[{"value":"27 February 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}