{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:12:26Z","timestamp":1757617946349,"version":"3.44.0"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T00:00:00Z","timestamp":1747785600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T00:00:00Z","timestamp":1747785600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["71971172","72371200"],"award-info":[{"award-number":["71971172","72371200"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002663","name":"Northwestern Polytechnical University","doi-asserted-by":"publisher","award":["23GH030611"],"award-info":[{"award-number":["23GH030611"]}],"id":[{"id":"10.13039\/501100002663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2025,7]]},"DOI":"10.1007\/s10878-025-01302-6","type":"journal-article","created":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T16:30:45Z","timestamp":1747845045000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The independent quadratic assignment problem: complexity and polynomially solvable special cases"],"prefix":"10.1007","volume":"49","author":[{"given":"Ante","family":"\u0106usti\u0107","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wei","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3864-0834","authenticated-orcid":false,"given":"Yang","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abraham P.","family":"Punnen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,5,21]]},"reference":[{"key":"1302_CR1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2023.100812","volume":"51","author":"L Waddell","year":"2024","unstructured":"Waddell L, Adams W (2024) Characterizing linearizable QAPs by the level-1 reformulation-linearization technique. Discrete Opt 51:100812","journal-title":"Discrete Opt"},{"key":"1302_CR2","first-page":"73","volume":"3","author":"T Akiyama","year":"1980","unstructured":"Akiyama T, Nishizeki T, Saito N (1980) NP-completeness of the hamiltonian cycle problem for bipartite graphs. J Inf Process 3:73\u201376","journal-title":"J Inf Process"},{"key":"1302_CR3","unstructured":"Baltz A (2001) Algorithmic and probabilistic aspects of the bipartite traveling salesman problem, PhD Dissertation, Christian-AlbrechtsUniversit\u00a8at zu Kiel, Kiel"},{"key":"1302_CR4","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1016\/j.orl.2004.08.002","volume":"33","author":"A Baltz","year":"2005","unstructured":"Baltz A, Sirvastav A (2005) Approximation algorithms for the Euclidean bipartite TSP. Operations Res Lett 33:403\u2013410","journal-title":"Operations Res Lett"},{"key":"1302_CR5","doi-asserted-by":"publisher","first-page":"2841","DOI":"10.1016\/j.disc.2010.06.037","volume":"310","author":"DK Benvenuti","year":"2010","unstructured":"Benvenuti DK, Punnen AP (2010) SC-Hamiltonian graphs and digraphs: new necessary conditions and impacts. Discrete Math 310:2841\u20132846","journal-title":"Discrete Math"},{"key":"1302_CR6","doi-asserted-by":"publisher","first-page":"2035","DOI":"10.1137\/070705775","volume":"23","author":"DK Benvenuti","year":"2010","unstructured":"Benvenuti DK, Punnen AP (2010) SC-Hamiltonicity and its linkages with strong Hamiltonicity of a graph. SIAM J Discrete Math 23:2035\u20132041","journal-title":"SIAM J Discrete Math"},{"key":"1302_CR7","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1016\/0377-2217(79)90143-7","volume":"3","author":"X Berenguer","year":"1979","unstructured":"Berenguer X (1979) A characterization of linear admissible transformations for the m-travelling salesmen problem. European J Operation Res 3:232\u2013238","journal-title":"European J Operation Res"},{"key":"1302_CR8","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/BF01585868","volume":"82","author":"R Burkard","year":"1998","unstructured":"Burkard R, \u00c7ela E, Rote G, Woeginger GJ (1998) The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: easy and hard cases. Math Programm 82:125\u2013158","journal-title":"Math Programm"},{"key":"1302_CR9","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898717754","volume-title":"Assignment Problems","author":"RE Burkard","year":"2009","unstructured":"Burkard RE, Dell\u2019Amico M, Martello S (2009) Assignment Problems. SIAM, Philadelphia"},{"key":"1302_CR10","doi-asserted-by":"crossref","unstructured":"Burkard RE, \u00c7ela E, Pardalos PM, Pitsoulis LS (1998) The quadratic assignment problem. In: Du, DZ., Pardalos, P.M. (eds) Handbook of Combinatorial Optimization, Springer, Boston, MA","DOI":"10.1007\/978-1-4613-0303-9_27"},{"key":"1302_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2787-6","volume-title":"The quadratic assignment problem: Theory and Algorithms","author":"E \u00c7ela","year":"1998","unstructured":"\u00c7ela E (1998) The quadratic assignment problem: Theory and Algorithms. Kluwer Academic Publishers, Dordrecht"},{"key":"1302_CR12","doi-asserted-by":"publisher","first-page":"1269","DOI":"10.1007\/s10878-014-9821-2","volume":"31","author":"E \u00c7ela","year":"2016","unstructured":"\u00c7ela E, De\u012dneko VG, Woeginger GJ (2016) Linearizable special cases of the QAP. J Combinat Opt 31:1269\u20131279","journal-title":"J Combinat Opt"},{"key":"1302_CR13","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.disopt.2016.01.004","volume":"19","author":"A \u0106usti\u0107","year":"2016","unstructured":"\u0106usti\u0107 A, Klinz B (2016) The constant objective value property for multidimensional assignment problems. Discrete Opt 19:23\u201335","journal-title":"Discrete Opt"},{"key":"1302_CR14","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/s10107-017-1111-1","volume":"166","author":"A \u0106usti\u0107","year":"2017","unstructured":"\u0106usti\u0107 A, Sokol V, Punnen AP, Bhattacharya B (2017) The Bilinear assignment problem: complexity and polynomially solvable special cases. Math Programm 166:185\u2013205","journal-title":"Math Programm"},{"key":"1302_CR15","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1016\/j.orl.2017.03.004","volume":"45","author":"A \u0106usti\u0107","year":"2017","unstructured":"\u0106usti\u0107 A, Punnen AP (2017) Average value of solutions of the bipartite quadratic assignment problem and linkages to domination analysis. Operations Res Lett 45:232\u2013237","journal-title":"Operations Res Lett"},{"key":"1302_CR16","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1007\/s10878-017-0184-3","volume":"35","author":"A \u0106usti\u0107","year":"2018","unstructured":"\u0106usti\u0107 A, Punnen AP (2018) Characterization of the linearizable instances of the quadratic minimum spanning tree problem. J Combinat Opt 35:436\u2013453","journal-title":"J Combinat Opt"},{"key":"1302_CR17","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1007\/s101070050010","volume":"87","author":"VG De\u012dneko","year":"2000","unstructured":"De\u012dneko VG, Woeginger GJ (2000) A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem. Math Programm 87:519\u2013542","journal-title":"Math Programm"},{"key":"1302_CR18","doi-asserted-by":"crossref","unstructured":"De\u012dneko, VG, Woeginger GJ. Another look at the shoelace TSP: The case of very old shoes, In: Ferro, A., Luccio, F., Widmayer, P. (eds) Fun with Algorithms. FUN 2014. Lecture Notes in Computer Science, vol 8496. Springer","DOI":"10.1007\/978-3-319-07890-8_11"},{"key":"1302_CR19","unstructured":"Frank A, Korte B, Triesch E, Vygen J (1998) On the bipartite travelling salesman problem, Report No. 98866-OR, Research Institute for Discrete Mathematics, University of Bonn"},{"key":"1302_CR20","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/0377-2217(83)90078-4","volume":"13","author":"AM Frieze","year":"1983","unstructured":"Frieze AM (1983) Complexity of a $$3$$-dimensional assignment problem. European J Operational Res 13:161\u2013164","journal-title":"European J Operational Res"},{"key":"1302_CR21","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1007\/BF01585532","volume":"7","author":"AM Frieze","year":"1974","unstructured":"Frieze AM (1974) A bilinear programming formulation of the 3-dimensional assignment problem. Math Programm 7:376\u2013379","journal-title":"Math Programm"},{"key":"1302_CR22","first-page":"128","volume":"5","author":"E Gabovich","year":"1976","unstructured":"Gabovich E (1976) Constant discrete programming problems on substitution sets, Translated from. Kibernetika 5:128\u2013134","journal-title":"Kibernetika"},{"key":"1302_CR23","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1016\/j.ejor.2016.07.060","volume":"257","author":"A Garc\u00eda","year":"2017","unstructured":"Garc\u00eda A, Tejel J (2017) Polynomially solvable cases of the bipartite traveling salesman problem. European J Operational Res 257:429\u2013438","journal-title":"European J Operational Res"},{"key":"1302_CR24","unstructured":"Gutin G, Punnen AP (editors) (2002) The traveling salesman problem and its variations, Kluwer Academic Publishers,"},{"key":"1302_CR25","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1016\/S0166-218X(03)00359-7","volume":"129","author":"G Gutin","year":"2003","unstructured":"Gutin G, Vainshtein A, Yeo A (2003) Domination analysis of combinatorial optimization problems. Discrete Appl Math 129:513\u2013520","journal-title":"Discrete Appl Math"},{"key":"1302_CR26","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:107\u2013116","journal-title":"Discrete Appl Math"},{"key":"1302_CR27","doi-asserted-by":"publisher","first-page":"754","DOI":"10.1287\/moor.1110.0509","volume":"36","author":"SN Kabadi","year":"2011","unstructured":"Kabadi SN, Punnen AP (2011) An $$O(n^4)$$ algorithm for the QAP linearization problem. Math Operations Res 36:754\u2013761","journal-title":"Math Operations Res"},{"key":"1302_CR28","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/S0012-365X(03)00041-4","volume":"271","author":"SN Kabadi","year":"2003","unstructured":"Kabadi SN, Punnen AP (2003) Weighted graphs with Hamiltonian cycles of same length. Discrete Math 271:129\u2013139","journal-title":"Discrete Math"},{"key":"1302_CR29","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/BF01580380","volume":"11","author":"H Konno","year":"1976","unstructured":"Konno H (1976) Maximization of a convex quadratic function under linear constraints. Math Programm 11:117\u2013127","journal-title":"Math Programm"},{"key":"1302_CR30","doi-asserted-by":"publisher","first-page":"53","DOI":"10.2307\/1907742","volume":"25","author":"TC Koopmans","year":"1957","unstructured":"Koopmans TC, Beckmann M (1957) Assignment problems and the location of economic activities. Econometrica 25:53\u201376","journal-title":"Econometrica"},{"key":"1302_CR31","doi-asserted-by":"publisher","first-page":"586","DOI":"10.1287\/mnsc.9.4.586","volume":"9","author":"EL Lawler","year":"1963","unstructured":"Lawler EL (1963) The quadratic assignment problem. Manag Sci 9:586\u2013599","journal-title":"Manag Sci"},{"key":"1302_CR32","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.disopt.2019.03.004","volume":"33","author":"S Lendl","year":"2019","unstructured":"Lendl S, Custic A, Punnen AP (2019) Combinatorial optimization with interaction costs: complexity and solvable cases. Discrete Opt 33:101\u2013117","journal-title":"Discrete Opt"},{"key":"1302_CR33","doi-asserted-by":"publisher","first-page":"1096","DOI":"10.1007\/s10878-020-00547-7","volume":"39","author":"F Meijer","year":"2020","unstructured":"Meijer F, Sotirov R (2020) The quadratic cycle cover problem: special cases and efficient bounds. J Combinat Opt 39:1096\u20131128","journal-title":"J Combinat Opt"},{"key":"1302_CR34","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0012-365X(95)00057-4","volume":"156","author":"H Muller","year":"1996","unstructured":"Muller H (1996) Hamiltonian circuits in chordal bipartite graphs. Discrete Math 156:291\u2013298","journal-title":"Discrete Math"},{"key":"1302_CR35","doi-asserted-by":"crossref","unstructured":"Punnen AP (ed) (2022) The Quadratic Unconstrained Binary Optimization Problem: Theory, Algorithms, and Applications, Springer","DOI":"10.1007\/978-3-031-04520-2"},{"key":"1302_CR36","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1016\/j.disopt.2013.02.003","volume":"10","author":"AP Punnen","year":"2013","unstructured":"Punnen AP, Kabadi SN (2013) A linear time algorithm for the Koopmans-Beckman QAP linearization and related problems. Discrete Opt 10:200\u2013209","journal-title":"Discrete Opt"},{"key":"1302_CR37","unstructured":"Punnen AP, Walter M, Woods B (2017) A characterization of linearizable instances of the quadratic travelling salesman problem, arXiv:1708.07217 [cs.DM]"},{"key":"1302_CR38","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1016\/j.ejor.2015.10.006","volume":"250","author":"AP Punnen","year":"2016","unstructured":"Punnen AP, Wang Y (2016) The bipartite boolean quadratic assignment program and extensions. European J Operational Res 250:715\u2013725","journal-title":"European J Operational Res"},{"key":"1302_CR39","doi-asserted-by":"publisher","first-page":"730","DOI":"10.1287\/ijoc.2019.0893","volume":"32","author":"V Sokol","year":"2020","unstructured":"Sokol V, \u0106usti\u0107 A, Punnen AP, Bhattacharya B (2020) Bilinear assignment problem: large neighborhoods and experimental analysis of algorithms. INFORMS J Comput 32:730\u2013746","journal-title":"INFORMS J Comput"},{"key":"1302_CR40","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1016\/0377-2217(95)00161-1","volume":"94","author":"A Torki","year":"1996","unstructured":"Torki A, Yajima Y, Enkawa T (1996) A low-rank bilinear programming approach for sub-optimal solution of the quadratic assignment problem. European J Operational Res 94:384\u2013391","journal-title":"European J Operational Res"},{"key":"1302_CR41","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0360-8352(90)90128-9","volume":"19","author":"LY Tsui","year":"1990","unstructured":"Tsui LY, Chang C-H (1990) A microcomputer based decision support tool for assigning dock doors in freight yards. Comput Indus Eng 19:309\u2013312","journal-title":"Comput Indus Eng"},{"key":"1302_CR42","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1016\/0360-8352(92)90117-3","volume":"23","author":"LY Tsui","year":"1992","unstructured":"Tsui LY, Chang C-H (1992) An optimal solution to a dock door assignment problem. Comput Indus Eng 23:283\u2013286","journal-title":"Comput Indus Eng"},{"key":"1302_CR43","doi-asserted-by":"publisher","first-page":"979","DOI":"10.1287\/ijoc.2020.1003","volume":"33","author":"Y Wang","year":"2021","unstructured":"Wang Y, Yang W, Punnen AP, Tian J, Yin A, Lu Z (2021) The rank one quadratic assignment problem. INFORMS J Comput 33:979\u2013996","journal-title":"INFORMS J Comput"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01302-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-025-01302-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01302-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T15:14:22Z","timestamp":1757171662000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-025-01302-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,21]]},"references-count":43,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["1302"],"URL":"https:\/\/doi.org\/10.1007\/s10878-025-01302-6","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2025,5,21]]},"assertion":[{"value":"11 April 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no Conflict of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"70"}}