{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T01:41:59Z","timestamp":1779154919390,"version":"3.51.4"},"reference-count":93,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2022,9,30]],"date-time":"2022-09-30T00:00:00Z","timestamp":1664496000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,9,30]],"date-time":"2022-09-30T00:00:00Z","timestamp":1664496000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,12]]},"DOI":"10.1007\/s10878-022-00907-5","type":"journal-article","created":{"date-parts":[[2022,9,30]],"date-time":"2022-09-30T16:02:54Z","timestamp":1664553774000},"page":"3711-3734","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Using the method of conditional expectations to supply an improved starting point for CCLS"],"prefix":"10.1007","volume":"44","author":[{"given":"Daniel","family":"Berend","sequence":"first","affiliation":[]},{"given":"Shahar","family":"Golan","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2764-3642","authenticated-orcid":false,"given":"Yochai","family":"Twitto","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,9,30]]},"reference":[{"issue":"1","key":"907_CR1","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/s10472-016-9515-9","volume":"79","author":"A Abram\u00e9","year":"2017","unstructured":"Abram\u00e9 A, Habet D, Toumi D (2017) Improving configuration checking for satisfiable random k-SAT instances. Ann Math Artif Intell 79(1):5\u201324","journal-title":"Ann Math Artif Intell"},{"key":"907_CR2","first-page":"245","volume":"185","author":"D Achlioptas","year":"2009","unstructured":"Achlioptas D (2009) Random satisfiability. Handb Satisf 185:245","journal-title":"Handb Satisf"},{"issue":"4","key":"907_CR3","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-SAT is $$2^{k} \\text{ log } 2 - O(k)$$. J Am Math Soc 17(4):947\u2013973","journal-title":"J Am Math Soc"},{"issue":"1","key":"907_CR4","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/S0166-218X(99)00138-9","volume":"99","author":"E Angel","year":"2000","unstructured":"Angel E, Zissimopoulos V (2000) On the classification of NP-complete problems in terms of their correlation coefficient. Discrete Appl Math 99(1):261\u2013277","journal-title":"Discrete Appl Math"},{"issue":"1","key":"907_CR5","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0304-3975(00)00239-5","volume":"263","author":"E Angel","year":"2001","unstructured":"Angel E, Zissimopoulos V (2001) On the landscape ruggedness of the quadratic assignment problem. Theoret Comput Sci 263(1):159\u2013172","journal-title":"Theoret Comput Sci"},{"key":"907_CR6","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/j.artint.2013.01.002","volume":"196","author":"C Ans\u00f3tegui","year":"2013","unstructured":"Ans\u00f3tegui C, Bonet ML, Levy J (2013) SAT-based MaxSAT algorithms. Artif Intell 196:77\u2013105","journal-title":"Artif Intell"},{"key":"907_CR7","doi-asserted-by":"crossref","unstructured":"Ans\u00f3tegui C, Bonet ML, Levy J (2009) Solving (weighted) partial MaxSAT through satisfiability testing. In: International conference on theory and applications of satisfiability testing. Springer, pp 427\u2013440","DOI":"10.1007\/978-3-642-02777-2_39"},{"key":"907_CR8","doi-asserted-by":"crossref","unstructured":"Ans\u00f3tegui, C, Bonet ML, Gabas J, Levy J (2012) Improving SAT-based weighted MaxSAT solvers. In: International conference on principles and practice of constraint programming. Springer, pp 86\u2013 101","DOI":"10.1007\/978-3-642-33558-7_9"},{"key":"907_CR9","unstructured":"Argelich J, Li CM, Many\u00e0 F, Planes J (2020) MaxSat evaluations. https:\/\/maxsat-evaluations.github.io\/"},{"key":"907_CR10","volume-title":"Complexity and approximation: combinatorial optimization problems and their approximability properties","author":"G Ausiello","year":"2003","unstructured":"Ausiello G, Crescenzi P, Gambosi G, Kann V, M-Spaccamela A, Protasi M (2003) Complexity and approximation: combinatorial optimization problems and their approximability properties, 2nd edn. Springer, New York","edition":"2"},{"key":"907_CR11","first-page":"8","volume":"2020","author":"F Avellaneda","year":"2020","unstructured":"Avellaneda F (2020) A short description of the solver EvalMaxSAT. MaxSAT Eval 2020:8","journal-title":"MaxSAT Eval"},{"key":"907_CR12","unstructured":"Berend D, Twitto Y (2020) Effect of initial assignment on local search performance for Max Sat. In: Proceedings of the 18th international symposium on experimental algorithms (SEA 2020), vol 160. Leibniz international proceedings in informatics (LIPIcs), pp 8:1\u2013 8:14"},{"key":"907_CR13","doi-asserted-by":"crossref","unstructured":"Berend D, Twitto Y (2016) The normalized autocorrelation length of random Max r-Sat converges in probability to (1 $$-$$ 1\/2$$^{r})$$\/r\u201d. In: The 19th international conference on theory and applications of satisfiability testing (SAT 2016). Springer, pp 60\u201376","DOI":"10.1007\/978-3-319-40970-2_5"},{"key":"907_CR14","first-page":"13","volume":"2017","author":"J Berg","year":"2017","unstructured":"Berg J, Korhonen T, J\u00e4rvisalo M (2017) Loandra: PMRES extended with preprocessing entering MaxSAT evaluation 2017. MaxSAT Eval 2017:13","journal-title":"MaxSAT Eval"},{"key":"907_CR15","volume-title":"Handbook of satisfiability","author":"A Biere","year":"2009","unstructured":"Biere A, Heule M, van Maaren H (2009) Handbook of satisfiability, vol 185. IOS Press, Amsterdam"},{"issue":"1","key":"907_CR16","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/s10479-005-5724-z","volume":"134","author":"P-T de Boer","year":"2005","unstructured":"de Boer P-T, Kroese DP, Mannor S, Rubinstein RY (2005) A tutorial on the cross-entropy method. Ann Oper Res 134(1):19\u201367","journal-title":"Ann Oper Res"},{"issue":"11","key":"907_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11432-018-9786-2","volume":"62","author":"N Bouhmala","year":"2019","unstructured":"Bouhmala N (2019) A Kernighan-Lin inspired algorithm for MAX-SAT. Sci China Inf Sci 62(11):1\u20133","journal-title":"Sci China Inf Sci"},{"issue":"3","key":"907_CR18","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/s10732-015-9284-3","volume":"21","author":"S Cai","year":"2015","unstructured":"Cai S, Jie Z, Su K (2015) An effective variable selection heuristic in SLS for weighted Max-2-SAT. J Heuristics 21(3):433\u2013456","journal-title":"J Heuristics"},{"key":"907_CR19","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.artint.2013.09.001","volume":"204","author":"S Cai","year":"2013","unstructured":"Cai S, Su K (2013) Local search for Boolean Satisfiability with configuration checking and subscore. Artif Intell 204:75\u201398","journal-title":"Artif Intell"},{"key":"907_CR20","doi-asserted-by":"crossref","unstructured":"Cai S, Su K (2011) Local search with configuration checking for SAT. In 2011 IEEE 23rd international conference on tools with artificial intelligence. IEEE, pp 59\u201366","DOI":"10.1109\/ICTAI.2011.18"},{"key":"907_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.artint.2016.07.006","volume":"240","author":"S Cai","year":"2016","unstructured":"Cai S, Luo C, Lin J, Su K (2016) New local search methods for partial MaxSAT. Artif Intell 240:1\u201318","journal-title":"Artif Intell"},{"key":"907_CR22","doi-asserted-by":"crossref","unstructured":"Cai S, Luo C, Thornton J, Su K (2014) Tailoring local search for Partial MaxSAT. In: Proceedings of the 28th AAAI conference on artificial intelligence. AAAI\u201914. AAAI Press, Qu\u00e9bec City, Qu\u00e9bec, pp 2623\u20132629","DOI":"10.1609\/aaai.v28i1.9109"},{"key":"907_CR23","unstructured":"Cha B, Iwama K, Kambayashi Y, Miyazaki S (1997) Local search algorithms for partial MAXSAT. In: AAAI\u201997\/IAAI\u201997, pp 263\u2013268"},{"issue":"1\u20133","key":"907_CR24","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"},{"key":"907_CR25","doi-asserted-by":"crossref","unstructured":"Chen R, Santhanam R (2015) Improved algorithms for sparse MAXSAT and MAX-k-CSP. In: Proceedings of the 18th international conference on theory and applications of satisfiability testing (SAT 2015). Springer, pp 33\u201345","DOI":"10.1007\/978-3-319-24318-4_4"},{"issue":"4","key":"907_CR26","doi-asserted-by":"publisher","first-page":"698","DOI":"10.1016\/j.aml.2011.09.053","volume":"25","author":"F Chicano","year":"2012","unstructured":"Chicano F, Luque G, Alba E (2012) Autocorrelation measures for the quadratic assignment problem. Appl Math Lett 25(4):698\u2013705","journal-title":"Appl Math Lett"},{"key":"907_CR27","doi-asserted-by":"crossref","unstructured":"Chicano F, Luque G, Alba E (2013) Problem understanding through landscape theory. In: Proceedings of the 15th annual conference companion on genetic and evolutionary computation. ACM, pp 1055\u2013 1062","DOI":"10.1145\/2464576.2482683"},{"key":"907_CR28","doi-asserted-by":"crossref","unstructured":"Chv\u00e1tal V, Reed B (1992) Mick gets some (the odds are on his side) (satisfiability). In: Proceedings of the 33rd annual symposium on foundations of computer science. IEEE, pp 620\u2013627","DOI":"10.1109\/SFCS.1992.267789"},{"key":"907_CR29","doi-asserted-by":"crossref","unstructured":"Coja-Oghlan A (2014) The asymptotic k-SAT threshold. In: Proceedings of the 46th annual ACM symposium on theory of computing. ACM, pp 804\u2013813","DOI":"10.1145\/2591796.2591822"},{"issue":"4","key":"907_CR30","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1002\/rsa.20015","volume":"24","author":"D Coppersmith","year":"2004","unstructured":"Coppersmith D, Gamarnik D, Hajiaghayi M, Sorkin GB (2004) Random MAX SAT, random MAX CUT, and their phase transitions. Random Struct Algorithms 24(4):502\u2013545","journal-title":"Random Struct Algorithms"},{"key":"907_CR31","doi-asserted-by":"crossref","unstructured":"Costello KP, Shapira A, Tetali P (2011) Randomized greedy: new variants of some classic approximation algorithms. In: Proceedings of the 22nd annual ACM-SIAM symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, pp 647\u2013655","DOI":"10.1137\/1.9781611973082.50"},{"issue":"1\u20132","key":"907_CR32","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0004-3702(95)00046-1","volume":"81","author":"JM Crawford","year":"1996","unstructured":"Crawford JM, Auton LD (1996) Experimental results on the crossover point in random 3-SAT. Artif Intell 81(1\u20132):31\u201357","journal-title":"Artif Intell"},{"key":"907_CR33","unstructured":"Davies J (2013) Solving MaxSAT by decoupling optimization and satisfaction. PhD thesis. University of Toronto"},{"key":"907_CR34","doi-asserted-by":"crossref","unstructured":"Davies J, Bacchus F (2011) Solving MAXSAT by solving a sequence of simpler SAT instances. In: Proceedings of the 17th international conference on principles and practice of constraint programming. Springer, pp 225\u2013239","DOI":"10.1007\/978-3-642-23786-7_19"},{"key":"907_CR35","doi-asserted-by":"crossref","unstructured":"Den Besten M, St\u00fctzle T, Dorigo M (2001) Design of iterated local search algorithms. In: Workshops on applications of evolutionary computation. Springer, pp 441\u2013451","DOI":"10.1007\/3-540-45365-2_46"},{"key":"907_CR36","doi-asserted-by":"crossref","unstructured":"Ding J, Sly A, Sun N (2015) Proof of the satisfiability conjecture for large k. In Proceedings of the 47th annual ACM symposium on theory of computing (STOC\u201915), pp 59\u201368","DOI":"10.1145\/2746539.2746619"},{"issue":"2","key":"907_CR37","doi-asserted-by":"publisher","first-page":"627","DOI":"10.1016\/j.cor.2012.08.021","volume":"40","author":"X Dong","year":"2013","unstructured":"Dong X, Chen P, Huang H, Nowak M (2013) A multi-restart iterated local search algorithm for the Permutation Flow Shop problem minimizing total flow time. Comput Oper Res 40(2):627\u2013632","journal-title":"Comput Oper Res"},{"issue":"3","key":"907_CR38","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1016\/0097-3165(73)90005-8","volume":"14","author":"P Erd\u00f6s","year":"1973","unstructured":"Erd\u00f6s P, Selfridge JL (1973) On a combinatorial game. J Comb Theory Ser A 14(3):298\u2013301","journal-title":"J Comb Theory Ser A"},{"issue":"3","key":"907_CR39","doi-asserted-by":"publisher","first-page":"2083","DOI":"10.1103\/PhysRevE.47.2083","volume":"47","author":"W Fontana","year":"1993","unstructured":"Fontana W, Stadler PF, Bornberg-Bauer EG, Griesmacher T, Hofacker IL, Tacker M, Tarazona P, Weinberger ED, Schuster P (1993) RNA folding and combinatory landscapes. Phys Rev E 47(3):2083\u20132099","journal-title":"Phys Rev E"},{"issue":"1","key":"907_CR40","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0166-218X(83)90017-3","volume":"5","author":"J Franco","year":"1983","unstructured":"Franco J, Paull M (1983) Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem. Discrete Appl Math 5(1):77\u201387","journal-title":"Discrete Appl Math"},{"issue":"4","key":"907_CR41","doi-asserted-by":"publisher","first-page":"1017","DOI":"10.1090\/S0894-0347-99-00305-7","volume":"12","author":"E Friedgut","year":"1999","unstructured":"Friedgut E, Bourgain J (1999) Sharp thresholds of graph properties, and the k-SAT problem. J Am Math Soc 12(4):1017\u20131054","journal-title":"J Am Math Soc"},{"key":"907_CR42","unstructured":"Goldberg DE (1988) Genetic algorithms and Walsh functions: a gentle introduction. Department of Mechanical Engineering, University of Alabama, Clearinghouse for Genetic Algorithms"},{"key":"907_CR43","doi-asserted-by":"crossref","unstructured":"Guerreiro AP, Terra-Neves M, Lynce I, Figueira JR, Manquinho V (2019) Constraint-based techniques in stochastic local search MaxSAT solving. In: International conference on principles and practice of constraint programming. Springer, pp 232\u2013250","DOI":"10.1007\/978-3-030-30048-7_14"},{"key":"907_CR44","volume-title":"The traveling salesman problem and its variations","author":"G Gutin","year":"2006","unstructured":"Gutin G, Punnen AP (2006) The traveling salesman problem and its variations. Springer, New York"},{"issue":"1\u20132","key":"907_CR45","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0166-218X(01)00267-0","volume":"119","author":"G Gutin","year":"2002","unstructured":"Gutin G, Yeo A (2002) Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number. Discrete Appl Math 119(1\u20132):107\u2013116","journal-title":"Discrete Appl Math"},{"key":"907_CR46","doi-asserted-by":"crossref","unstructured":"Hains D, Whitley D, Howe A, Chen W (2013) Hyperplane initialized local search for MAXSAT. In Proceedings of the 15th annual conference on genetic and evolutionary computation, pp 805\u2013812","DOI":"10.1145\/2463372.2463468"},{"issue":"5","key":"907_CR47","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1145\/1506409.1506429","volume":"52","author":"JA Halderman","year":"2009","unstructured":"Halderman JA, Schoen SD, Heninger N, Clarkson W, Paul W, Calandrino JA, Feldman AJ, Appelbaum J, Felten EW (2009) Lest we remember: cold-boot attacks on encryption keys. Commun ACM 52(5):91\u201398","journal-title":"Commun ACM"},{"issue":"4","key":"907_CR48","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 (JACM) 48(4):798\u2013859","journal-title":"J ACM (JACM)"},{"key":"907_CR49","unstructured":"Heckendorn RB, Rana S, Whitley D (1999) Polynomial time summary statistics for a generalization of MAXSAT. In: Proceedings of the 11th annual conference on genetic and evolutionary computation. Morgan Kaufmann, pp 281\u2013288"},{"key":"907_CR50","unstructured":"Heninger NA (2011) Error correction and the cryptographic key. PhD thesis. Princeton University"},{"key":"907_CR51","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1613\/jair.2347","volume":"31","author":"F Heras","year":"2008","unstructured":"Heras F, Larrosa J, Oliveras A (2008) MiniMaxSAT: an efficient weighted Max-SAT solver. J Artif Intell Res (JAIR) 31:1\u201332","journal-title":"J Artif Intell Res (JAIR)"},{"key":"907_CR52","doi-asserted-by":"crossref","unstructured":"Hoos HH, Smyth K, St\u00fctzle T (2004) Search space features underlying the performance of stochastic local search algorithms for MAXSAT. In: Proceedings of the 8th international conference on parallel problem solving from nature (PPSN VIII). Springer, pp 51\u201360","DOI":"10.1007\/978-3-540-30217-9_6"},{"key":"907_CR53","volume-title":"Stochastic local search: foundations and applications","author":"HH Hoos","year":"2004","unstructured":"Hoos HH, St\u00fctzle T (2004) Stochastic local search: foundations and applications. Elsevier, New York"},{"key":"907_CR54","unstructured":"Kamal AA (2012) Cryptanalysis and secure implementation of modern cryptographic algorithms. PhD thesis. Concordia University"},{"key":"907_CR55","doi-asserted-by":"crossref","unstructured":"Kamal AA, Youssef AM (2010) Applications of SAT solvers to AES key recovery from decayed key schedule images. In: Proceedings of the 4th international conference on emerging security information, systems and technologies. IEEE, pp 216\u2013220","DOI":"10.1109\/SECURWARE.2010.42"},{"issue":"1\u20132","key":"907_CR56","first-page":"95","volume":"8","author":"M Koshimura","year":"2012","unstructured":"Koshimura M, Zhang T, Fujita H, Hasegawa R (2012) QMaxSAT: a partial Max-SAT solver. J Satisf Boolean Model Comput 8(1\u20132):95\u2013100","journal-title":"J Satisf Boolean Model Comput"},{"issue":"2\u20133","key":"907_CR57","first-page":"59","volume":"7","author":"D Le Berre","year":"2010","unstructured":"Le Berre D, Parrain A (2010) The Sat4j library, release 2.2. J Satisf Boolean Model Comput 7(2\u20133):59\u201364","journal-title":"J Satisf Boolean Model Comput"},{"key":"907_CR58","first-page":"613","volume-title":"Handbook of satisfiability","author":"CM Li","year":"2009","unstructured":"Li CM, Many\u00e0 F (2009) MaxSAT, hard and soft constraints. In: Biere A, Heule MJH, van Maaren H, Walsh T (eds) Handbook of satisfiability, vol 185. IOS Press, Amsterdam, pp 613\u2013631"},{"key":"907_CR59","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1613\/jair.2215","volume":"30","author":"CM Li","year":"2007","unstructured":"Li CM, Manya F, Planes J (2007) New inference rules for Max-SAT. J Artif Intell Res 30:321\u2013359","journal-title":"J Artif Intell Res"},{"issue":"4","key":"907_CR60","doi-asserted-by":"publisher","first-page":"982","DOI":"10.1007\/s00453-022-00938-8","volume":"84","author":"W Li","year":"2022","unstructured":"Li W, Xu C, Yang Y, Chen J, Wang J (2022) A refined branching algorithm for the maximum satisfiability problem. Algorithmica 84(4):982\u20131006","journal-title":"Algorithmica"},{"key":"907_CR61","unstructured":"Liao X (2013) Maximum satisfiability approach to game theory and network security. PhD thesis. Kyushu University"},{"key":"907_CR62","doi-asserted-by":"crossref","unstructured":"Liao X, Zhang H, Koshimura M, Fujita H, Hasegawa R (2013) Using MaxSAT to correct errors in AES key schedule images. In: 2013 IEEE 25th international conference on tools with artificial intelligence. IEEE, pp 284\u2013291","DOI":"10.1109\/ICTAI.2013.51"},{"key":"907_CR63","doi-asserted-by":"crossref","unstructured":"Louren\u00e7o HR, Martin OC, St\u00fctzle T (2019) Iterated local search: framework and applications. In Handbook of metaheuristics. Springer, pp 129\u2013168","DOI":"10.1007\/978-3-319-91086-4_5"},{"issue":"7","key":"907_CR64","doi-asserted-by":"publisher","first-page":"1830","DOI":"10.1109\/TC.2014.2346196","volume":"64","author":"C Luo","year":"2014","unstructured":"Luo C, Cai S, Wu W, Jie Z, Su K-W (2014) CCLS: an efficient local search algorithm for weighted maximum satisfiability. IEEE Trans Comput 64(7):1830\u20131843","journal-title":"IEEE Trans Comput"},{"issue":"5","key":"907_CR65","first-page":"1028","volume":"45","author":"C Luo","year":"2014","unstructured":"Luo C, Cai S, Su K, Wu W (2014) Clause states based configuration checking in local search for satisfiability. IEEE Trans Cybern 45(5):1028\u20131041","journal-title":"IEEE Trans Cybern"},{"key":"907_CR66","doi-asserted-by":"crossref","unstructured":"Luo C, Cai S, Wu W, Su K (2013) Focused random walk with configuration checking and break minimum for satisfiability. In: International conference on principles and practice of constraint programming. Springer, pp 481\u2013496","DOI":"10.1007\/978-3-642-40627-0_37"},{"key":"907_CR67","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/j.ins.2013.04.015","volume":"241","author":"KM Malan","year":"2013","unstructured":"Malan KM, Engelbrecht AP (2013) A survey of techniques for characterising fitness landscapes and some possible ways forward. Inf Sci 241:148\u2013163","journal-title":"Inf Sci"},{"issue":"1","key":"907_CR68","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/BF02601639","volume":"63","author":"OC Martin","year":"1996","unstructured":"Martin OC, Otto SW (1996) Combining simulated annealing with local search heuristics. Ann Oper Res 63(1):57\u201375","journal-title":"Ann Oper Res"},{"issue":"3","key":"907_CR69","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1002\/rsa.20090","volume":"28","author":"S Mertens","year":"2006","unstructured":"Mertens S, M\u00e9zard M, Zecchina R (2006) Threshold values of random K-SAT from the cavity method. Random Struct Algorithms 28(3):340\u2013373","journal-title":"Random Struct Algorithms"},{"key":"907_CR70","first-page":"245","volume-title":"New ideas in optimization","author":"P Merz","year":"1999","unstructured":"Merz P, Freisleben B (1999) Fitness landscapes and memetic algorithm design. In: Corne D, Dorigo M, Glover F, Dasgupta D, Moscato P, Poli R, Price KV (eds) New ideas in optimization. McGraw-Hill, London, pp 245\u2013260"},{"issue":"5582","key":"907_CR71","doi-asserted-by":"publisher","first-page":"812","DOI":"10.1126\/science.1073287","volume":"297","author":"M M\u00e9zard","year":"2002","unstructured":"M\u00e9zard M, Parisi G, Zecchina R (2002) Analytic and algorithmic solution of random satisfiability problems. Science 297(5582):812\u2013815","journal-title":"Science"},{"issue":"12","key":"907_CR72","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1023\/A:1006343127545","volume":"24","author":"P Mills","year":"2000","unstructured":"Mills P, Tsang E (2000) Guided local search for solving SAT and weighted MAX-SAT problems. J Autom Reason 24(12):205\u2013223","journal-title":"J Autom Reason"},{"key":"907_CR73","doi-asserted-by":"crossref","unstructured":"Nadel A (2019) TT-Open-WBO-Inc: tuning polarity and variable selection for anytime SAT-based optimization. In: Proceedings of the MaxSAT evaluations","DOI":"10.3233\/SAT-200126"},{"key":"907_CR74","doi-asserted-by":"crossref","unstructured":"Narodytska N, Bacchus F (2014) Maximum Satisfiability using core-guided MaxSAT resolution. In Proceedings of the 28th AAAI conference on artificial intelligence. AAAI Press, pp 2717\u20132723","DOI":"10.1609\/aaai.v28i1.9124"},{"issue":"1","key":"907_CR75","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":"907_CR76","doi-asserted-by":"crossref","unstructured":"Pankratov D, Borodin A (2010) On the relative merits of simple local search methods for the MAX-SAT problem. In: Proceedings of the 13th international conference on theory and applications of satisfiability testing (SAT 2010). SAT\u201910. Springer, pp 223\u2013236","DOI":"10.1007\/978-3-642-14186-7_19"},{"key":"907_CR77","first-page":"20","volume":"2018","author":"T Paxian","year":"2018","unstructured":"Paxian T, Reimer S, Becker B (2018) Pacose: an iterative SAT-based MaxSAT solver. MaxSAT Eval 2018:20","journal-title":"MaxSAT Eval"},{"key":"907_CR78","doi-asserted-by":"crossref","unstructured":"Pipatsrisawat K, Darwiche A (2007) Clone: solving weighted Max-SAT in a reduced search space. In: Australasian joint conference on artificial intelligence. Springer, pp 223\u2013233","DOI":"10.1007\/978-3-540-76928-6_24"},{"key":"907_CR79","doi-asserted-by":"crossref","unstructured":"Poloczek M (2011) Bounds on greedy algorithms for MAX SAT. In Proceedings of the 19th European symposium on algorithms. ESA\u201911. Springer, pp 37\u201348","DOI":"10.1007\/978-3-642-23719-5_4"},{"key":"907_CR80","doi-asserted-by":"crossref","unstructured":"Poloczek M, Williamson DP (2016) An experimental evaluation of fast approximation algorithms for the maximum satisfiability problem. In: International symposium on experimental algorithms. Springer, pp 246\u2013261","DOI":"10.1007\/978-3-319-38851-9_17"},{"issue":"3","key":"907_CR81","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":"3","key":"907_CR82","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1109\/TEVC.2011.2163638","volume":"16","author":"A Pr\u00fcgel-Bennett","year":"2012","unstructured":"Pr\u00fcgel-Bennett A, Tayarani-Najaran M-H (2012) Maximum satisfiability: anatomy of the fitness landscape for a hard combinatorial optimization problem. IEEE Trans Evol Comput 16(3):319\u2013338","journal-title":"IEEE Trans Evol Comput"},{"issue":"4","key":"907_CR83","doi-asserted-by":"publisher","first-page":"518","DOI":"10.1109\/TEVC.2009.2033579","volume":"14","author":"M Qasem","year":"2010","unstructured":"Qasem M, Pr\u00fcgel-Bennett A (2010) Learning the large-scale structure of the MAX-SAT landscape using populations. IEEE Trans Evol Comput 14(4):518\u2013529","journal-title":"IEEE Trans Evol Comput"},{"key":"907_CR84","doi-asserted-by":"crossref","unstructured":"Selman B, Kautz HA, Cohen B (1996) Local search strategies for satisfiability testing. In: DIMACS series in discrete mathematics and theoretical computer science, pp 521\u2013532","DOI":"10.1090\/dimacs\/026\/25"},{"key":"907_CR85","unstructured":"Selman B, Kautz HA, Cohen B (1994) Noise strategies for improving local search. In: Proceedings of the 12th national conference on artificial intelligence, vol 1. American Association for Artificial Intelligence, pp 337\u2013343"},{"key":"907_CR86","unstructured":"Selman B, Levesque H, Mitchell D (1992) A new method for solving hard satisfiability problems. In: Proceedings of the 10th national conference on artificial intelligence. AAAI Press, pp 440\u2013446"},{"key":"907_CR87","doi-asserted-by":"crossref","unstructured":"Smyth K, Hoos HH, St\u00fctzle T (2003) Iterated robust tabu search for MAX-SAT. In: Conference of the Canadian society for computational studies of intelligence. Springer, pp 129\u2013144","DOI":"10.1007\/3-540-44886-1_12"},{"key":"907_CR88","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/3-540-45692-9_10","volume-title":"Biological evolution and statistical physics","author":"P Stadler","year":"2002","unstructured":"Stadler P (2002) Fitness landscapes. In: L\u00e4ssig M, Valleriani A (eds) Biological evolution and statistical physics. Springer, New York, pp 183\u2013204"},{"key":"907_CR89","unstructured":"Sun Grid Engine (SGE) QuickStart (2020) http:\/\/star.mit.edu\/cluster\/docs\/0.93.3\/guides\/sge.html"},{"key":"907_CR90","doi-asserted-by":"crossref","unstructured":"Sutton AM, Whitley LD, Howe AE (2009) A polynomial time computation of the exact correlation structure of k-satisfiability landscapes. In: proceedings of the 11th annual conference on genetic and evolutionary computation. ACM, pp 365\u2013372","DOI":"10.1145\/1569901.1569952"},{"key":"907_CR91","doi-asserted-by":"crossref","unstructured":"Tompkins DA, Hoos HH (2005) UBCSAT: An implementation and experimentation environment for SLS algorithms for SAT and MAXSAT. In: Proceedings of the 8th international conference on theory and applications of satisfiability testing. Springer, pp 306\u2013320","DOI":"10.1007\/11527695_24"},{"key":"907_CR92","doi-asserted-by":"crossref","unstructured":"Xiao M (2022) An exact MaxSAT algorithm: further observations and further improvements. Preprint, accepted to IJCAI","DOI":"10.24963\/ijcai.2022\/262"},{"issue":"3","key":"907_CR93","doi-asserted-by":"publisher","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 Algorithms 17(3):475\u2013502","journal-title":"J Algorithms"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00907-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-022-00907-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00907-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,30]],"date-time":"2022-10-30T10:20:04Z","timestamp":1667125204000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-022-00907-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,30]]},"references-count":93,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["907"],"URL":"https:\/\/doi.org\/10.1007\/s10878-022-00907-5","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,30]]},"assertion":[{"value":"1 September 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 September 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}