{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T10:46:13Z","timestamp":1768473973625,"version":"3.49.0"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030226282","type":"print"},{"value":"9783030226299","type":"electronic"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","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":[[2019]]},"DOI":"10.1007\/978-3-030-22629-9_17","type":"book-chapter","created":{"date-parts":[[2019,6,12]],"date-time":"2019-06-12T00:02:42Z","timestamp":1560297762000},"page":"232-246","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Dynamic Sparsification for Quadratic Assignment Problems"],"prefix":"10.1007","author":[{"given":"Maximilian","family":"John","sequence":"first","affiliation":[]},{"given":"Andreas","family":"Karrenbauer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,6,12]]},"reference":[{"key":"17_CR1","first-page":"43","volume-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","author":"Warren Adams","year":"1994","unstructured":"Adams, W., Johnson, T.: Improved linear programming-based lower bounds for the quadratic assignment problem. DIMACS 512 Ser. Discret. Math. Theor. Comput. Sci. 16, 43\u201377 (1994). \n                      https:\/\/doi.org\/10.1090\/dimacs\/016\/02"},{"key":"17_CR2","unstructured":"AFNOR: Interfaces utilisateurs - Dispositions de clavier bureautique fran\u00e7ais, NF Z71\u2013300 Avril 2019"},{"issue":"1","key":"17_CR3","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/S0020-0190(00)00151-4","volume":"77","author":"EM Arkin","year":"2001","unstructured":"Arkin, E.M., Hassin, R., Sviridenko, M.: Approximating the maximum quadratic assignment problem. Inf. Process. Lett. 77(1), 13\u201316 (2001). \n                      https:\/\/doi.org\/10.1016\/S0020-0190(00)00151-4","journal-title":"Inf. Process. Lett."},{"key":"17_CR4","first-page":"147","volume":"5","author":"D Birkhoff","year":"1946","unstructured":"Birkhoff, D.: Tres observaciones sobre el algebra lineal. Universidad Nacional de Tucuman Revista Serie A 5, 147\u2013151 (1946)","journal-title":"Universidad Nacional de Tucuman Revista Serie A"},{"key":"17_CR5","doi-asserted-by":"publisher","first-page":"1713","DOI":"10.1007\/978-1-4613-0303-9_27","volume-title":"Handbook of Combinatorial Optimization","author":"Rainer E. Burkard","year":"1998","unstructured":"Burkard, R.E., \u00c7ela, E., Pardalos, P.M., Pitsoulis, L.S.: The Quadratic Assignment Problem, pp. 1713\u20131809. Springer, Boston (1998). \n                      https:\/\/doi.org\/10.1007\/978-1-4613-0303-9_27"},{"key":"17_CR6","first-page":"121","volume":"21","author":"R Burkard","year":"1977","unstructured":"Burkard, R., Offermann, J.: Entwurf von Schreibmaschinentastaturen mittels quadratischer Zuordnungsprobleme. Zeitschrift f\u00fcr Oper. Res. 21, 121\u2013132 (1977)","journal-title":"Zeitschrift f\u00fcr Oper. Res."},{"key":"17_CR7","unstructured":"DGLFLF: Rapport au Parlement sur l\u2019emploi de la langue fran\u00e7aise. Government Report (2015). \n                      http:\/\/www.culture.gouv.fr\/Thematiques\/Langue-francaise-et-langues-de-France\/La-DGLFLF\/Nos-priorites\/Rapport-au-Parlement-sur-l-emploi-de-la-langue-francaise-2015\n                      \n                    . From the D\u00e9l\u00e9gation g\u00e9n\u00e9rale \u00e0 la langue fran\u00e7aise et aux langues de France of the Minist\u00e8re de la Culture et de la Communication (in French)"},{"key":"17_CR8","unstructured":"DGLFLF: Vers une norme fran\u00e7aise pour les claviers informatiques. Government Publication (2016). \n                      http:\/\/www.culture.gouv.fr\/Thematiques\/Langue-francaise-et-langues-de-France\/Politiques-de-la-langue\/Langues-et-numerique\/Les-technologies-de-la-langue-et-la-normalisation\/Vers-une-norme-francaise-pour-les-claviers-informatiques\n                      \n                    . From the D\u00e9l\u00e9gation g\u00e9n\u00e9rale \u00e0 la langue fran\u00e7aise et aux langues de France of the Minist\u00e8re de la Culture et de la Communication (in French)"},{"key":"17_CR9","unstructured":"Feit, A.M.: Assignment Problems for Optimizing Text Input. G5 artikkeliv\u00e4it\u00f6skirja (2018). \n                      http:\/\/urn.fi\/URN:ISBN:978-952-60-8016-1"},{"issue":"1","key":"17_CR10","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/0166-218X(83)90018-5","volume":"5","author":"A Frieze","year":"1983","unstructured":"Frieze, A., Yadegar, J.: On the quadratic assignment problem. Discrete Appl. Math. 5(1), 89\u201398 (1983). \n                      https:\/\/doi.org\/10.1016\/0166-218X(83)90018-5","journal-title":"Discrete Appl. Math."},{"key":"17_CR11","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1137\/0110022","volume":"10","author":"PC Gilmore","year":"1962","unstructured":"Gilmore, P.C.: Optimal and suboptimal algorithms for the quadratic assignment problem. SIAM J. Appl. Math. 10, 305\u2013313 (1962)","journal-title":"SIAM J. Appl. Math."},{"key":"17_CR12","unstructured":"Gurobi Optimization, L.: Gurobi Optimizer Version 8.1 (2019). \n                      http:\/\/www.gurobi.com"},{"key":"17_CR13","unstructured":"Huber, C., Riedl, W.: The Quadratic Assignment Problem: the Linearization of Xia and Yuan is Weaker than the Linearization of Adams and Johnson and a Family of Cuts to Narrow the Gap, preprint on webpage at \n                      https:\/\/arxiv.org\/abs\/1710.02472"},{"key":"17_CR14","first-page":"414","volume-title":"Lecture Notes in Computer Science","author":"Maximilian John","year":"2016","unstructured":"John, M., Karrenbauer, A.: A Novel SDP Relaxation for the Quadratic Assignment Problem Using Cut Pseudo Bases, pp. 414\u2013425. Springer, Cham (2016). \n                      https:\/\/doi.org\/10.1007\/978-3-319-45587-7_36"},{"issue":"3","key":"17_CR15","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/0377-2217(78)90095-4","volume":"2","author":"L Kaufman","year":"1978","unstructured":"Kaufman, L., Broeckx, F.: An algorithm for the quadratic assignment problem using Benders\u2019 decomposition. Eur. J. Oper. Res. 2(3), 207\u2013211 (1978). \n                      https:\/\/doi.org\/10.1016\/0377-2217(78)90095-4","journal-title":"Eur. J. Oper. Res."},{"key":"17_CR16","unstructured":"Koopmans, T., Beckmann, M.J.: Assignment Problems and the Location of Economic Activities. Cowles Foundation Discussion Papers 4, Cowles Foundation for Research in Economics, Yale University (1955). \n                      http:\/\/EconPapers.repec.org\/RePEc:cwl:cwldpp:4"},{"issue":"4","key":"17_CR17","doi-asserted-by":"publisher","first-page":"586","DOI":"10.1287\/mnsc.9.4.586","volume":"9","author":"EL Lawler","year":"1963","unstructured":"Lawler, E.L.: The quadratic assignment problem. Manag. Sci. 9(4), 586\u2013599 (1963). \n                      https:\/\/doi.org\/10.1287\/mnsc.9.4.586","journal-title":"Manag. Sci."},{"key":"17_CR18","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1007\/978-1-4613-3632-7_12","volume-title":"Large Scale Optimization","author":"Yusin Lee","year":"1994","unstructured":"Lee, Y., Orlin, J.B.: On Very Large Scale Assignment Problems, pp. 206\u2013244. Springer, Boston (1994). \n                      https:\/\/doi.org\/10.1007\/978-1-4613-3632-7_12"},{"issue":"1","key":"17_CR19","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1287\/opre.16.1.150","volume":"16","author":"C Nugent","year":"1968","unstructured":"Nugent, C., Vollman, T., Ruml, J.: An experimental comparison of techniques for the assignment of facilities to locations. Oper. Res. 16(1), 150\u2013173 (1968). \n                      https:\/\/doi.org\/10.1287\/opre.16.1.150","journal-title":"Oper. Res."},{"issue":"1","key":"17_CR20","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/s12532-010-0012-6","volume":"2","author":"J Peng","year":"2010","unstructured":"Peng, J., Mittelmann, H., Li, X.: A new relaxation framework for quadratic assignment problems based on matrix splitting. Math. Program. Comput. 2(1), 59\u201377 (2010). \n                      https:\/\/doi.org\/10.1007\/s12532-010-0012-6","journal-title":"Math. Program. Comput."},{"key":"17_CR21","unstructured":"Pollatschek, M., Gershoni, N., Radday, Y.: Optimization of the typewriter keyboard by simulation. Angewandte Mathematik 10 (1976)"},{"issue":"3","key":"17_CR22","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/j.disopt.2009.01.002","volume":"6","author":"J Povh","year":"2009","unstructured":"Povh, J., Rendl, F.: Copositive and Semidefinite relaxations of the quadratic assignment problem. Discret. Optim. 6(3), 231\u2013241 (2009). \n                      https:\/\/doi.org\/10.1016\/j.disopt.2009.01.002","journal-title":"Discret. Optim."},{"issue":"5","key":"17_CR23","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0167-6377(86)90007-6","volume":"4","author":"M Queyranne","year":"1986","unstructured":"Queyranne, M.: Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems. Oper. Res. Lett. 4(5), 231\u2013234 (1986). \n                      https:\/\/doi.org\/10.1016\/0167-6377(86)90007-6","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"17_CR24","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/0166-218X(92)00190-W","volume":"52","author":"HD Sherali","year":"1994","unstructured":"Sherali, H.D., Adams, W.P.: A hierarchy of relaxations and convex hull characterizations for mixed-integer zero-one programming problems. Discret. Appl. Math. 52(1), 83\u2013106 (1994). \n                      https:\/\/doi.org\/10.1016\/0166-218X(92)00190-W","journal-title":"Discret. Appl. Math."},{"issue":"5","key":"17_CR25","doi-asserted-by":"publisher","first-page":"805","DOI":"10.1080\/10556780500273077","volume":"21","author":"Y Xia","year":"2006","unstructured":"Xia, Y., Yuan, Y.X.: A new linearization method for quadratic assignment problems. Optim. Methods Softw. 21(5), 805\u2013818 (2006). \n                      https:\/\/doi.org\/10.1080\/10556780500273077","journal-title":"Optim. Methods Softw."},{"key":"17_CR26","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/s10479-012-1079-4","volume":"207","author":"H Zhang","year":"2013","unstructured":"Zhang, H., Beltran-Royo, C., Ma, L.: Solving the quadratic assignment problem by means of general purpose mixed integer linear programming solvers. Ann. OR 207, 261\u2013278 (2013)","journal-title":"Ann. OR"},{"issue":"1","key":"17_CR27","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1023\/A:1009795911987","volume":"2","author":"Q Zhao","year":"1998","unstructured":"Zhao, Q., Karisch, S.E., Rendl, F., Wolkowicz, H.: Semidefinite programming relaxations for the quadratic assignment problem. J. Comb. Optim. 2(1), 71\u2013109 (1998). \n                      https:\/\/doi.org\/10.1023\/A:1009795911987","journal-title":"J. Comb. Optim."}],"container-title":["Lecture Notes in Computer Science","Mathematical Optimization Theory and Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-22629-9_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,12]],"date-time":"2019-06-12T00:04:15Z","timestamp":1560297855000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-22629-9_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030226282","9783030226299"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-22629-9_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"12 June 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"MOTOR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Mathematical Optimization Theory and Operations Research","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Ekaterinburg","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Russia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 July 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 July 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"motor2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/motor2019.uran.ru","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}