{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T06:02:34Z","timestamp":1740808954707,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540278290"},{"type":"electronic","value":"9783540315803"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11527695_14","type":"book-chapter","created":{"date-parts":[[2010,12,20]],"date-time":"2010-12-20T17:06:47Z","timestamp":1292864807000},"page":"173-182","source":"Crossref","is-referenced-by-count":3,"title":["Approximation Algorithm for Random MAX-kSAT"],"prefix":"10.1007","author":[{"given":"Yannet","family":"Interian","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"1-2","key":"14_CR1","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0304-3975(01)00159-1","volume":"265","author":"D. Achlioptas","year":"2001","unstructured":"Achlioptas, D.: Lower Bounds for Random 3-SAT via Differential Equations. Theoretical Computer Science\u00a0265(1-2), 159\u2013185 (2001)","journal-title":"Theoretical Computer Science"},{"key":"14_CR2","unstructured":"Achlioptas, D., Naor, A., Peres, Y.: On the Fraction of Satisfiable Clauses in Typical Formulas. In: Extended Abstract in FOCS 2003, pp. 362\u2013370 (2003)"},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"Achlioptas, D., Sorkin, G.B.: Optimal Myopic Algorithms for Random 3-SAT. In: Proceedings of FOCS 2000, pp. 590\u2013600 (2000)","DOI":"10.1109\/SFCS.2000.892327"},{"key":"14_CR4","unstructured":"Broder, A.Z., Frieze, A.M., Upfal, E.: On the satisfiability and maximum satisfiability of random 3-CNF formulas. In: Proc. 4th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 322\u2013330 (1993)"},{"issue":"4","key":"14_CR5","doi-asserted-by":"publisher","first-page":"1106","DOI":"10.1137\/0215080","volume":"15","author":"M.-T. Chao","year":"1986","unstructured":"Chao, M.-T., Franco, J.: Probability analysis of two heuristics for the 3-satisfiability problem. SIAM J. Comput.\u00a015(4), 1106\u20131118 (1986)","journal-title":"SIAM J. Comput."},{"key":"14_CR6","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0020-0255(90)90030-E","volume":"51","author":"M.T. Chao","year":"1990","unstructured":"Chao, M.T., Franco, J.: Probabilistic analysis of a generalization of the unit clause selection heuristic for the k-satisfiability problem. Information Sciences\u00a051, 289\u2013314 (1990)","journal-title":"Information Sciences"},{"key":"14_CR7","unstructured":"de la Vega Fernandez, W., Karpinski, M.: 9\/8-Approximation Algorithm for Random MAX-3SAT. In: Electronic Colloquium on Computational Complexity (ECCC), p. 70 (2002)"},{"key":"14_CR8","doi-asserted-by":"crossref","unstructured":"Kaporis, A.C., Kirousis, L.M., Lalas, E.G.: The probabilistic analysis of a greedy satisfiability algorithm. In: 10th Annual European Symposium on Algorithms, Rome, Italy (2002)","DOI":"10.1007\/3-540-45749-6_51"},{"key":"14_CR9","doi-asserted-by":"crossref","unstructured":"Kaporis, A.C., Kirousis, L.M., Lalas, E.: Selecting complementary pairs of literals. Electronic Notes in Discrete Mathematics\u00a016 (2003)","DOI":"10.1016\/S1571-0653(04)00462-7"},{"key":"14_CR10","unstructured":"Kaporis, A.C., Kirousis, L.M., Stamatiou, Y.C.: How to prove conditional randomness using the Principle of Deferred Decisions. Technical Report, Computer Technology Institute, Greece (2002), Available at: http:\/\/www.ceid.upatras.gr\/faculty\/kirousis\/kks-pdd02.ps"},{"key":"14_CR11","unstructured":"Mitchell, D., Selman, B., Levesque, H.: Hard and easy distributions of sat problems. In: Proc. 10-th National Conf. on Artificial Intelligence (AAAI 1992), pp. 459\u2013465 (1992)"},{"key":"14_CR12","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, D., Levesque, H.: Generating Hard Satisfiability Problems. Artificial Intelligence\u00a081, 17\u201329 (1996)","journal-title":"Artificial Intelligence"},{"issue":"4","key":"14_CR13","doi-asserted-by":"publisher","first-page":"1217","DOI":"10.1214\/aoap\/1177004612","volume":"5","author":"N.C. Wormald","year":"1995","unstructured":"Wormald, N.C.: Differential equations for random processes and random graphs. Ann. Appl. Probab.\u00a05(4), 1217\u20131235, 36 (1995)","journal-title":"Ann. Appl. Probab."}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11527695_14.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,28]],"date-time":"2025-02-28T23:57:06Z","timestamp":1740787026000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11527695_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540278290","9783540315803"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/11527695_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}