{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T19:37:34Z","timestamp":1771702654129,"version":"3.50.1"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2006,6,1]],"date-time":"2006-06-01T00:00:00Z","timestamp":1149120000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Appl Intell"],"published-print":{"date-parts":[[2006,6]]},"DOI":"10.1007\/s10489-006-8514-7","type":"journal-article","created":{"date-parts":[[2006,4,18]],"date-time":"2006-04-18T20:46:36Z","timestamp":1145393196000},"page":"227-239","source":"Crossref","is-referenced-by-count":19,"title":["An effective heuristic algorithm for the maximum satisfiability problem"],"prefix":"10.1007","volume":"24","author":[{"given":"Mohamed El Bachir","family":"Mena\u00ef","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohamed","family":"Batouche","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"8514_CR1","doi-asserted-by":"crossref","unstructured":"Arora S, Lund C, Motwani R, Sudan M, Szegedy M (1992) Proof verification and hardness of approximation problems. In: Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science, pp. 14\u201323","DOI":"10.1109\/SFCS.1992.267823"},{"key":"8514_CR2","doi-asserted-by":"crossref","first-page":"4083","DOI":"10.1103\/PhysRevLett.71.4083","volume":"71","author":"P Bak","year":"1993","unstructured":"Bak P, Sneppen K (1993) Punctuated equilibrium and criticality in a simple model of evolution. Phys Rev Lett 71:4083\u20134086","journal-title":"Phys Rev Lett."},{"issue":"23","key":"8514_CR3","first-page":"5211","volume":"86","author":"P Bak","year":"1987","unstructured":"Bak P, Tang C, Wiesenfeld K (1987) Self-organized criticality: An explanation of 1\/f-noise. Phys Rev Lett 86:(23) 5211\u20135214","journal-title":"Phys Rev Lett."},{"key":"8514_CR4","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/264216.264220","volume":"2","author":"R Battiti","year":"1997","unstructured":"Battiti R, Protasi M (1997) Reactive Search, a history-sensitive heuristic for MAX-SAT. ACM J Exper Algors 2:2","journal-title":"ACM J Exper Algors"},{"key":"8514_CR5","doi-asserted-by":"crossref","first-page":"1109","DOI":"10.1088\/0305-4470\/35\/5\/301","volume":"35","author":"S Boettcher","year":"2002","unstructured":"Boettcher S, Grigni M (2002) Jamming model for the Extremal Optimization heuristic. J Phys A: Math. Gen. 35:1109\u20131123","journal-title":"J Phys A: Math. Gen."},{"key":"8514_CR6","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/S0004-3702(00)00007-2","volume":"119","author":"S Boettcher","year":"2000","unstructured":"Boettcher S, Percus AG (2000) Nature\u2019s way of optimizing Elsevier Science Art Intell 119:275\u2013286","journal-title":"Elsevier Science Art Intell."},{"issue":"23","key":"8514_CR7","doi-asserted-by":"crossref","first-page":"5211","DOI":"10.1103\/PhysRevLett.86.5211","volume":"86","author":"S Boettcher","year":"2001","unstructured":"Boettcher S, Percus AG (2001) Optimization with extremal dynamics. Phys Rev Lett, 86(23):5211\u20135214","journal-title":"Phys Rev Lett."},{"issue":"026114","key":"8514_CR8","first-page":"1","volume":"64","author":"S Boettcher","year":"2001","unstructured":"Boettcher S, Percus AG (2001) Extremal Optimization for graph partitioning. Phys Rev E 64(026114):1\u201313","journal-title":"Phys Rev E"},{"key":"8514_CR9","unstructured":"Cha B, Iwama K, Kambayashi Y, Miyazaki S (1997) Local search algorithms for partial MAXSAT. In: Proceedings of the 14th National Conference on Artificial (AAAI-97), Providence, Rhode Island, USA, pp 263\u2013268"},{"key":"8514_CR10","doi-asserted-by":"crossref","unstructured":"Cook SA (1971) The complexity of theorem proving procedures. In: Proceedings of the 3rd Annual ACM Symposium of the Theory of Computation, pp 151\u2013158","DOI":"10.1145\/800157.805047"},{"issue":"4","key":"8514_CR11","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1145\/306198.306210","volume":"29","author":"P Crescenzi","year":"1998","unstructured":"Crescenzi P, Kann V (1998) How to find the best approximation results\u2014a follow-up to Garey and Johnson. ACM SIGACT News 29(4):90\u201397","journal-title":"ACM SIGACT News"},{"key":"8514_CR12","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/321033.321034","volume":"7","author":"M Davis","year":"1960","unstructured":"Davis M, Putnam H (1960) A computing procedure for quantification theory. J Assoc Comp Mach 7:201\u2013215","journal-title":"J Assoc Comp Mach."},{"key":"8514_CR13","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1006\/jagm.1997.0867","volume":"24","author":"O Dubois","year":"1997","unstructured":"Dubois O, Boufkhad Y (1997) A general upper bound of the satisfiability thresholds of random r-SAT formulae. J Algor 24:394\u2013420","journal-title":"J Algor."},{"key":"8514_CR14","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0020-0190(86)90051-7","volume":"23","author":"J Franco","year":"1986","unstructured":"Franco J (1986) On the probabilistic performance of algorithms for the satisfiability problem. Inform Proc Lett 23:103\u2013106","journal-title":"Inform Proc Lett."},{"key":"8514_CR15","unstructured":"Gent IP, Walsh T (1993) Towards an understanding of hill-climbing procedures for SAT. In: Proceedings of the 11th National Conference on Artificial Intelligence (AAAI-93), Washington DC, Washington, USA, pp. 28\u201333"},{"issue":"3","key":"8514_CR16","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1287\/ijoc.1.3.190","volume":"1","author":"F Glover","year":"1989","unstructured":"Glover F (1989) Tabu Search: Part I. ORSA J Comp 1(3):190\u2013206","journal-title":"ORSA J Comp"},{"issue":"1","key":"8514_CR17","first-page":"32","volume":"2","author":"F Glover","year":"1989","unstructured":"Glover F (1989) Tabu Search: Part II. ORSA Journal on Computing 2(1):+32","journal-title":"ORSA Journal on Computing"},{"key":"8514_CR18","doi-asserted-by":"crossref","unstructured":"Haken H, Wolf HC (1996) The physics of atoms and quanta, 5th edn. Springer-Verlag","DOI":"10.1007\/978-3-642-97689-6"},{"key":"8514_CR19","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BF02241270","volume":"44","author":"P Hansen","year":"1990","unstructured":"Hansen P, Jaumard B (1990) Algorithms for the maximum satisfiability problems. Computing 44:279\u2013303","journal-title":"Computing."},{"key":"8514_CR20","unstructured":"Jiang Y, Kautz HA, Selman B (1995) Solving problems with hard and soft constraints using a stochastic algorithm for MAX-SAT. In: Proceedings of the 1st International Joint Workshop on Artificial Intelligence and Operations Research, Oregon, USA, available at http:\/\/www.cirl.uoregon.edu\/aior\/"},{"key":"8514_CR21","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D Johnson","year":"1974","unstructured":"Johnson D (1974) Approximation algorithms for combinatorial problems. J Comp Sys Sci 9:256\u2013278","journal-title":"J Comp Sys Sci."},{"key":"8514_CR22","first-page":"1194","volume-title":"Proceedings of the 13th National Conference on Artificial Intelligence (AAAI-96)","author":"HA Kautz","year":"1996","unstructured":"Kautz HA, Selman B (1996) Pushing the envelope: Planning, propositional logic, and stochastic search. In: Proceedings of the 13th National Conference on Artificial Intelligence (AAAI-96), Portland, Oregon, USA, MIT Press vol. 2: pp 1194\u20131201"},{"key":"8514_CR23","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S Kirkpatrick","year":"1983","unstructured":"Kirkpatrick S, Gelatt CD, Vecchi PM (1983) Optimization by Simulated Annealing. Science 220:671\u2013680","journal-title":"Science"},{"key":"8514_CR24","unstructured":"Mazure B, Sais L, Gregoire E (1997) Tabu Search for SAT. In: Proceedings of the 14th National Conference on Artificial Intelligence (AAAI-97), Providence, Rhode Island, USA,pp 281\u2013285"},{"key":"8514_CR25","unstructured":"Mena\u00ed MB, Batouche M (2002) EO for MAXSAT. In: Proceedings of the International Conference on Artificial Intelligence (IC-AI\u201902) Las Vegas, Nevada, USA, vol. 3: pp 954\u2013958"},{"key":"8514_CR26","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1063\/1.1699114","volume":"21","author":"N Metropolis","year":"1953","unstructured":"Metropolis N, Rosenbluth AW, Rosenbluth MN, Teller AH, Teller E (1953) Equation of state calculations by fast computing machines. J Chem Phys 21:1087\u20131092","journal-title":"J Chem Phys"},{"key":"8514_CR27","unstructured":"Mitchell D, Selman B, Levesque HJ (1992) Hard and easy distributions of SAT problems. In: Proceedings of the 10th National Conference on Artificial Intelligence (AAAI-92), San Jose, CA, USA, pp 459\u2013465"},{"key":"8514_CR28","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1038\/22055","volume":"400","author":"R Monasson","year":"1999","unstructured":"Monasson R, Zecchina R, Kirkpatrick S, Selman B, Troyansky L (1999) Determining computational complexity from characteristic \u2018Phase Transition\u2019. Nature 400:133\u2013137","journal-title":"Nature."},{"key":"8514_CR29","doi-asserted-by":"crossref","first-page":"599","DOI":"10.1016\/S0377-2217(97)00294-4","volume":"106","author":"K Nonobe","year":"1998","unstructured":"Nonobe K, Ibaraki T (1998) A Tabu Search approach to the CSP (Constraint Satisfaction Problem) as a general problem solver. European J Oper Res 106:599\u2013623","journal-title":"European J Oper Res."},{"key":"8514_CR30","doi-asserted-by":"crossref","unstructured":"Resende MGC, Pitsoulis LS, Pardalos PM (1997) Approximate solution of weighted MAX-SAT problems using GRASP. In: Satisfiability Problem: Theory and Applications, of DIMACS Series in Discrete Mathematics and Theoretical Computer Science (American Mathematical Society, 1997) 35:393\u2013405","DOI":"10.1090\/dimacs\/035\/11"},{"key":"8514_CR31","volume-title":"Introduction to Probability Models","author":"MS Ross","year":"2000","unstructured":"Ross MS (2000) Introduction to Probability Models, 7th edn. Academic Press, New York","edition":"7th edn."},{"key":"8514_CR32","unstructured":"Selman B, Kautz HA (1993) An empirical study of greedy local search for satisfiability testing. In: Proceedings of the 11th National Conference on Artificial Intelligence (AAAI-93), Washington DC, Washington, USA, pp 46\u201351"},{"key":"8514_CR33","unstructured":"Selman B, Kautz HA (1993) Domain independent extensions to GSAT: Solving large structured satisfiability problems. In: Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI-93), Chambery, France,pp. 290\u2013295"},{"key":"8514_CR34","unstructured":"Selman B, Kautz HA, Cohen B (1994) Noise strategies for improving local search. In: Proceedings of the 12th National Conference on Artificial Intelligence (AAAI-94), Seattle, Washington, USA, pp 337\u2013343"},{"key":"8514_CR35","doi-asserted-by":"crossref","unstructured":"Spears WM (1996) Simulated Annealing for hard satisfiability problems. In: Johnson DS, Trick MA (eds) Cliques, Coloring and Satisfiability: Second DIMACS Implementation Challenge, vol. 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science (American Mathematical Society), 553\u2013558","DOI":"10.1090\/dimacs\/026\/26"},{"key":"8514_CR36","volume-title":"How to find more efficient initial solution for searching, RUTCOR Research Report 49\u20132001","author":"S Szedmak","year":"2001","unstructured":"Szedmak S (2001) How to find more efficient initial solution for searching, RUTCOR Research Report 49-2001, Rutgers Center for Operations Research, Rutgers University, Piscataway, New Jersey, USA"},{"key":"8514_CR37","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1023\/A:1011306011437","volume":"7","author":"M Yagiura","year":"2001","unstructured":"Yagiura M, Ibaraki T (2001) Efficient 2 and 3-flip neighborhood search algorithms for the MAXSAT: Experimental evaluation. J Heur 7:423\u2013442","journal-title":"J Heur"},{"key":"8514_CR38","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1006\/jagm.1994.1045","volume":"17","author":"M Yannakakis","year":"1994","unstructured":"Yannakakis M (1994) On the approximation of maximum satisfiability. J Algor 17:475\u2013502","journal-title":"J Algor."},{"key":"8514_CR39","unstructured":"DIMACS. http:\/\/dimacs.rutgers.edu\/challenges\/"}],"container-title":["Applied Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10489-006-8514-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10489-006-8514-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10489-006-8514-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T18:25:39Z","timestamp":1559154339000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10489-006-8514-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,6]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,6]]}},"alternative-id":["8514"],"URL":"https:\/\/doi.org\/10.1007\/s10489-006-8514-7","relation":{},"ISSN":["0924-669X","1573-7497"],"issn-type":[{"value":"0924-669X","type":"print"},{"value":"1573-7497","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,6]]}}}