{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T16:17:48Z","timestamp":1742919468993,"version":"3.40.3"},"publisher-location":"Cham","reference-count":39,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319180076"},{"type":"electronic","value":"9783319180083"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-18008-3_13","type":"book-chapter","created":{"date-parts":[[2015,4,15]],"date-time":"2015-04-15T07:32:51Z","timestamp":1429083171000},"page":"182-198","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["An Efficient Local Search for Partial Latin Square Extension Problem"],"prefix":"10.1007","author":[{"given":"Kazuya","family":"Haraguchi","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,4,16]]},"reference":[{"key":"13_CR1","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1007\/s10732-007-9054-y","volume":"14","author":"B Alidaee","year":"2008","unstructured":"Alidaee, B., Kochenberger, G., Wang, H.: Simple and fast surrogate constraint heuristics for the maximum independent set problem. J. Heuristics 14, 571\u2013585 (2008)","journal-title":"J. Heuristics"},{"key":"13_CR2","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1007\/s10732-012-9196-4","volume":"18","author":"D Andrade","year":"2012","unstructured":"Andrade, D., Resende, M., Werneck, R.: Fast local search for the maximum independent set problem. J. Heuristics 18, 525\u2013547 (2012). the preliminary version appeared in Proc. 7th WEA (LNCS vol. 5038), pp. 220\u2013234 (2008)","journal-title":"J. Heuristics"},{"key":"13_CR3","unstructured":"Ans\u00f3tegui, C., Val, A., Dot\u00fa, I., Fern\u00e1ndez, C., Many\u00e1, F.: Modeling choices in quasigroup completion: SAT vs. CSP. In: Proc. National Conference on Artificial Intelligence, pp. 137\u2013142 (2004)"},{"issue":"2","key":"13_CR4","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1016\/j.ejor.2005.01.048","volume":"173","author":"G Appa","year":"2006","unstructured":"Appa, G., Magos, D., Mourtos, I.: Searching for mutually orthogonal latin squares via integer and constraint programming. European J. Operational Research 173(2), 519\u2013530 (2006)","journal-title":"European J. Operational Research"},{"issue":"5","key":"13_CR5","doi-asserted-by":"publisher","first-page":"891","DOI":"10.1109\/50.233253","volume":"11","author":"RA Barry","year":"1993","unstructured":"Barry, R.A., Humblet, P.A.: Latin routers, design and implementation. IEEE\/OSA J. Lightwave Technology 11(5), 891\u2013899 (1993)","journal-title":"IEEE\/OSA J. Lightwave Technology"},{"key":"13_CR6","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/11754602_12","volume-title":"Recent Advances in Constraints","author":"R Bart\u00e1k","year":"2006","unstructured":"Bart\u00e1k, R.: On generators of random quasigroup problems. In: Hnich, B., Carlsson, M., Fages, F., Rossi, F. (eds.) CSCLP 2005. LNCS (LNAI), vol. 3978, pp. 164\u2013178. Springer, Heidelberg (2006)"},{"key":"13_CR7","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/0166-218X(84)90075-1","volume":"8","author":"CJ Colbourn","year":"1984","unstructured":"Colbourn, C.J.: The complexity of completing partial latin squares. Discrete Applied Mathematics 8, 25\u201330 (1984)","journal-title":"Discrete Applied Mathematics"},{"key":"13_CR8","doi-asserted-by":"crossref","unstructured":"Colbourn, C.J., Dinitz, J.H.: Handbook of Combinatorial Designs. Chapman & Hall\/CRC, 2nd edn. (2006)","DOI":"10.1201\/9781420010541"},{"key":"13_CR9","doi-asserted-by":"crossref","unstructured":"Crawford, B., Aranda, M., Castro, C., Monfroy, E.: Using constraint programming to solve sudoku puzzles. In: Proc. ICCIT 2008, vol. 2, pp. 926\u2013931 (2008)","DOI":"10.1109\/ICCIT.2008.154"},{"key":"13_CR10","series-title":"Communications in Computer and Information Science","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/978-3-642-02298-2_52","volume-title":"Cutting-Edge Research Topics on Multiple Criteria Decision Making","author":"B Crawford","year":"2009","unstructured":"Crawford, B., Castro, C., Monfroy, E.: Solving sudoku with constraint programming. In: Shi, Y., Wang, S., Peng, Y., Li, J., Zeng, Y. (eds.) MCDM 2009. CCIS, vol. 35, pp. 345\u2013348. Springer, Heidelberg (2009)"},{"key":"13_CR11","doi-asserted-by":"crossref","unstructured":"Cygan, M.: Improved approximation for 3-dimensional matching via bounded pathwidth local search. In: Proc. FOCS 2013, pp. 509\u2013518 (2013)","DOI":"10.1109\/FOCS.2013.61"},{"key":"13_CR12","unstructured":"E\u00e9n, N., S\u00f6rensson, N.: The MiniSat Page, January 20, 2015. http:\/\/minisat.se\/Main.html"},{"key":"13_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"408","DOI":"10.1007\/978-3-319-09174-7_35","volume-title":"Combinatorial Optimization","author":"M F\u00fcrer","year":"2014","unstructured":"F\u00fcrer, M., Yu, H.: Approximating the k-set packing problem by local improvements. In: Fouilhoux, P., Gouveia, L.E.N., Mahjoub, A.R., Paschos, V.T. (eds.) ISCO 2014. LNCS, vol. 8596, pp. 408\u2013420. Springer, Heidelberg (2014)"},{"key":"13_CR14","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Company (1979)"},{"key":"13_CR15","doi-asserted-by":"crossref","unstructured":"Glover, F., Kochenberger, G. (eds.): Handbook of Metaheuristics. Kluwer Academic Publishers (2003)","DOI":"10.1007\/b101874"},{"issue":"5","key":"13_CR16","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1016\/j.orl.2003.09.007","volume":"32","author":"CP Gomes","year":"2004","unstructured":"Gomes, C.P., Regis, R.G., Shmoys, D.B.: An improved approximation algorithm for the partial latin square extension problem. Operations Research Letters 32(5), 479\u2013484 (2004)","journal-title":"Operations Research Letters"},{"key":"13_CR17","unstructured":"Gomes, C.P., Selman, B.: Problem structure in the presence of perturbations. In: Proc. AAAI-97, pp. 221\u2013227 (1997)"},{"key":"13_CR18","unstructured":"Gomes, C.P., Shmoys, D.B.: Completing quasigroups or latin squares: a structured graph coloring problem. In: Proc. Computational Symposium on Graph Coloring and Generalizations (2002)"},{"key":"13_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/978-3-540-24664-0_28","volume-title":"Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems","author":"C Gomes","year":"2004","unstructured":"Gomes, C., Sellmann, M., van Es, C., van Es, H.: The challenge of generating spatially balanced scientific experiment designs. In: R\u00e9gin, J.-C., Rueher, M. (eds.) CPAIOR 2004. LNCS, vol. 3011, pp. 387\u2013394. Springer, Heidelberg (2004)"},{"key":"13_CR20","unstructured":"Gonzalez, T.F. (ed.): Handbook of Approximation Algorithms and Metaheuristics. Chapman & Hall\/CRC (2007)"},{"key":"13_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1007\/978-3-540-70918-3_45","volume-title":"STACS 2007","author":"I Hajirasouliha","year":"2007","unstructured":"Hajirasouliha, I., Jowhari, H., Kumar, R., Sundaram, R.: On completing latin squares. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol. 4393, pp. 524\u2013535. Springer, Heidelberg (2007)"},{"issue":"8","key":"13_CR22","doi-asserted-by":"publisher","first-page":"1773","DOI":"10.1016\/j.dam.2008.11.013","volume":"157","author":"MM Halld\u00f3rsson","year":"2009","unstructured":"Halld\u00f3rsson, M.M., Losievskaja, E.: Independent sets in bounded-degree hypergraphs. Discrete Applied Mathematics 157(8), 1773\u20131786 (2009)","journal-title":"Discrete Applied Mathematics"},{"key":"13_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1007\/978-3-319-07890-8_19","volume-title":"Fun with Algorithms","author":"K Haraguchi","year":"2014","unstructured":"Haraguchi, K., Ono, H.: Approximability of latin square completion-type puzzles. In: Ferro, A., Luccio, F., Widmayer, P. (eds.) FUN 2014. LNCS, vol. 8496, pp. 218\u2013229. Springer, Heidelberg (2014)"},{"issue":"4","key":"13_CR24","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An $$n^{5\/2}$$ algorithm for maximum matchings in bipartite graphs. SIAM J. Computing 2(4), 225\u2013231 (1973)","journal-title":"SIAM J. Computing"},{"issue":"1","key":"13_CR25","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1137\/0402008","volume":"2","author":"CAJ Hurkens","year":"1989","unstructured":"Hurkens, C.A.J., Schrijver, A.: On the size of systems of sets every $$t$$ of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems. SIAM J. Discrete Mathematics 2(1), 68\u201372 (1989)","journal-title":"SIAM J. Discrete Mathematics"},{"key":"13_CR26","unstructured":"IBM ILOG CPLEX, January 20, 2015. http:\/\/www-01.ibm.com\/software\/commerce\/optimization\/cplex-optimizer\/"},{"key":"13_CR27","unstructured":"Itoyanagi, J., Hashimoto, H., Yagiura, M.: A local search algorithm with large neighborhoods for the maximum weighted independent set problem. In: Proc. MIC 2011, pp. 191\u2013200 (2011)"},{"issue":"2","key":"13_CR28","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1007\/PL00009274","volume":"24","author":"R Kumar","year":"1999","unstructured":"Kumar, R., Russel, A., Sundaram, R.: Approximating latin square extensions. Algorithmica 24(2), 128\u2013138 (1999)","journal-title":"Algorithmica"},{"key":"13_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1007\/11758501_86","volume-title":"Computational Science \u2013 ICCS 2006","author":"T Lambert","year":"2006","unstructured":"Lambert, T., Monfroy, E., Saubion, F.: A generic framework for local search: application to the sudoku problem. In: Alexandrov, V.N., van Albada, G.D., Sloot, P.M.A., Dongarra, J. (eds.) ICCS 2006. LNCS, vol. 3991, pp. 641\u2013648. Springer, Heidelberg (2006)"},{"key":"13_CR30","unstructured":"Le Bras, R., Perrault, A., Gomes, C.P.: Polynomial time construction for spatially balanced latin squares. Tech. rep., Computing and Information Science Technical Reports, Cornell University (2012). http:\/\/hdl.handle.net\/1813\/28697"},{"issue":"4","key":"13_CR31","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/s10732-007-9012-8","volume":"13","author":"R Lewis","year":"2007","unstructured":"Lewis, R.: Metaheuristics can solve sudoku puzzles. J. Heuristics 13(4), 387\u2013401 (2007)","journal-title":"J. Heuristics"},{"key":"13_CR32","unstructured":"LocalSolver, January 20, 2015. http:\/\/www.localsolver.com\/"},{"issue":"3","key":"13_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11432-011-4343-3","volume":"56","author":"F Ma","year":"2013","unstructured":"Ma, F., Zhang, J.: Finding orthogonal latin squares using finite model searching tools. Science China Information Sciences 56(3), 1\u20139 (2013)","journal-title":"Science China Information Sciences"},{"key":"13_CR34","unstructured":"Simonis, H.: Sudoku as a constraint problem, January 20, 2015. http:\/\/4c.ucc.ie\/ hsimonis\/sudoku.pdf"},{"key":"13_CR35","unstructured":"Smith, C., Gomes, C., Fernandez, C.: Streamlining local search for spatially balanced latin squares. In: Proc. IJCAI 2005, pp. 1539\u20131541 (2005)"},{"issue":"15","key":"13_CR36","doi-asserted-by":"publisher","first-page":"5817","DOI":"10.1016\/j.eswa.2013.05.019","volume":"40","author":"R Soto","year":"2013","unstructured":"Soto, R., Crawford, B., Galleguillos, C., Monfroy, E., Paredes, F.: A hybrid AC3-tabu search algorithm for solving sudoku puzzles. Expert Systems with Applications 40(15), 5817\u20135821 (2013)","journal-title":"Expert Systems with Applications"},{"key":"13_CR37","unstructured":"Tamura, N.: Sugar: a SAT-based Constraint Solver, January 20, 2015. http:\/\/bach.istc.kobe-u.ac.jp\/sugar\/"},{"key":"13_CR38","unstructured":"The International SAT Competitions, January 20, 2015. http:\/\/www.satcompetition.org\/"},{"key":"13_CR39","doi-asserted-by":"crossref","unstructured":"Vieira Jr., H., Sanchez, S., Kienitz, K.H., Belderrain, M.C.N.: Generating and improving orthogonal designs by using mixed integer programming. European J. Operational Research 215(3), 629\u2013638 (2011)","DOI":"10.1016\/j.ejor.2011.07.005"}],"container-title":["Lecture Notes in Computer Science","Integration of AI and OR Techniques in Constraint Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-18008-3_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,30]],"date-time":"2020-12-30T20:06:02Z","timestamp":1609358762000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-18008-3_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319180076","9783319180083"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-18008-3_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"16 April 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}