{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T06:33:38Z","timestamp":1757313218617,"version":"3.37.3"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2020,2,25]],"date-time":"2020-02-25T00:00:00Z","timestamp":1582588800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,2,25]],"date-time":"2020-02-25T00:00:00Z","timestamp":1582588800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100007659","name":"Tilburg University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100007659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2020,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The quadratic cycle cover problem is the problem of finding a set of node-disjoint cycles visiting all the nodes such that the total sum of interaction costs between consecutive arcs is minimized. In this paper we study the linearization problem for the quadratic cycle cover problem and related lower bounds. In particular, we derive various sufficient conditions for the quadratic cost matrix to be linearizable, and use these conditions to compute bounds. We also show how to use a sufficient condition for linearizability within an iterative bounding procedure. In each step, our algorithm computes the best equivalent representation of the quadratic cost matrix and its optimal linearizable matrix with respect to the given sufficient condition for linearizability. Further, we show that the classical Gilmore\u2013Lawler type bound belongs to the family of linearization based bounds, and therefore apply the above mentioned iterative reformulation technique. We also prove that the linearization vectors resulting from this iterative approach satisfy the constant value property. The best among here introduced bounds outperform existing lower bounds when taking both quality and efficiency into account.\n<\/jats:p>","DOI":"10.1007\/s10878-020-00547-7","type":"journal-article","created":{"date-parts":[[2020,2,25]],"date-time":"2020-02-25T18:02:51Z","timestamp":1582653771000},"page":"1096-1128","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["The quadratic cycle cover problem: special cases and efficient bounds"],"prefix":"10.1007","volume":"39","author":[{"given":"Frank","family":"de Meijer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Renata","family":"Sotirov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,2,25]]},"reference":[{"issue":"2","key":"547_CR1","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.disopt.2004.03.006","volume":"1","author":"WP Adams","year":"2004","unstructured":"Adams WP, Forrester RJ, Glover FW (2004) Comparisons and enhancement strategies for linearizing mixed 0\u20131 quadratic programs. Discrete Optim 1(2):99\u2013120","journal-title":"Discrete Optim"},{"issue":"10","key":"547_CR2","doi-asserted-by":"publisher","first-page":"1274","DOI":"10.1287\/mnsc.32.10.1274","volume":"32","author":"WP Adams","year":"1986","unstructured":"Adams WP, Sherali HD (1986) A tight linearization and an algorithm for zero\u2013one quadratic programming problems. Manag Sci 32(10):1274\u20131290","journal-title":"Manag Sci"},{"issue":"2","key":"547_CR3","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1287\/opre.38.2.217","volume":"38","author":"WP Adams","year":"1990","unstructured":"Adams WP, Sherali HD (1990) Linearization strategies for a class of zero\u2013one mixed integer programming problems. Oper Res 38(2):217\u2013226","journal-title":"Oper Res"},{"key":"547_CR4","doi-asserted-by":"publisher","first-page":"697","DOI":"10.1137\/S0097539796312721","volume":"29","author":"A Aggarwal","year":"1999","unstructured":"Aggarwal A, Coppersmith D, Khanna S, Motwani R, Schieber B (1999) The angular-metric traveling salesman problem. SIAM J Comput 29:697\u2013711","journal-title":"SIAM J Comput"},{"key":"547_CR5","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1002\/net.20423","volume":"57","author":"E Amaldi","year":"2011","unstructured":"Amaldi E, Galbiati G, Maffioli F (2011) On minimum reload cost paths, tours and flows. Networks 57:254\u2013260","journal-title":"Networks"},{"key":"547_CR6","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898717754","volume-title":"Assignment problems","author":"R Burkard","year":"2009","unstructured":"Burkard R, Dell\u2019Amico M, Martello S (2009) Assignment problems. SIAM, Philadelphia"},{"issue":"3","key":"547_CR7","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1002\/net.21884","volume":"74","author":"Y B\u00fcy\u00fck\u00e7olak","year":"2019","unstructured":"B\u00fcy\u00fck\u00e7olak Y, G\u00f6z\u00fcpek D, \u00d6zkan S (2019) On minimum reload cost paths, tours and flows. Networks 74(3):274\u2013286","journal-title":"Networks"},{"key":"547_CR8","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1287\/opre.40.1.S22","volume":"40","author":"P Carraresi","year":"1992","unstructured":"Carraresi P, Malucelli F (1992) A new lower bound for the quadratic assignment problem. Oper Res 40:22\u201327","journal-title":"Oper Res"},{"issue":"1","key":"547_CR9","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1137\/16M1108959","volume":"32","author":"S Chiba","year":"2018","unstructured":"Chiba S, Yamashita T (2018) On directed 2-factors in digraphs and 2-factors containing perfect matchings in bipartite graphs. SIAM J Discrete Math 32(1):394\u2013409","journal-title":"SIAM J Discrete Math"},{"issue":"4","key":"547_CR10","doi-asserted-by":"publisher","first-page":"1428","DOI":"10.1137\/07068446X","volume":"22","author":"FCD Comellas","year":"2008","unstructured":"Comellas FCD, Fiol MA (2008) Multidimensional manhattan street networks. SIAM J Discrete Math 22(4):1428\u20131447","journal-title":"SIAM J Discrete Math"},{"issue":"2","key":"547_CR11","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) A characterization of linearizable instances of the quadratic minimum spanning tree problem. J Comb Optim 35(2):436\u2013453","journal-title":"J Comb Optim"},{"key":"547_CR12","unstructured":"de Meijer F (2018) Bounds on the minimum reload cost cycle cover problem. Master\u2019s thesis, Tilburg University"},{"issue":"2","key":"547_CR13","first-page":"197","volume":"6","author":"P Erd\u0151s","year":"1959","unstructured":"Erd\u0151s P, R\u00e9nyi A (1959) On random graphs. Publ Math 6(2):197\u2013290","journal-title":"Publ Math"},{"key":"547_CR14","unstructured":"Fischer A (2013) A polyhedral study of quadratic traveling salesman problems. PhD thesis, Chemnitz University of Technology"},{"key":"547_CR15","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.dam.2013.09.011","volume":"166","author":"A Fischer","year":"2014","unstructured":"Fischer A, Fischer F, J\u00e4ger G, Keilwagen J, Molitor P, Grosse I (2014) Exact algorithms and heuristics for the quadratic traveling salesman problem with an application in bioinformatics. Discrete Appl Math 166:87\u2013114","journal-title":"Discrete Appl Math"},{"key":"547_CR16","first-page":"211","volume":"5165","author":"F Fischer","year":"2009","unstructured":"Fischer F, J\u00e4ger G, Lau A, Molitor P (2009) Complexity and algorithms for the traveling salesman problem and the assignment problem of second order. Lect Notes Comput Sci 5165:211\u2013224","journal-title":"Lect Notes Comput Sci"},{"key":"547_CR17","doi-asserted-by":"publisher","first-page":"3494","DOI":"10.1016\/j.dam.2008.02.013","volume":"156","author":"G Galbiati","year":"2008","unstructured":"Galbiati G (2008) The complexity of a minimum reload cost diameter problem. Discrete Appl Math 156:3494\u20133497","journal-title":"Discrete Appl Math"},{"key":"547_CR18","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1016\/j.dam.2011.12.006","volume":"164","author":"G Galbiati","year":"2014","unstructured":"Galbiati G, Gualandi S, Maffioli F (2014) On minimum reload cost cycle cover. Discrete Appl Math 164:112\u2013120","journal-title":"Discrete Appl Math"},{"key":"547_CR19","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1002\/net.20443","volume":"59","author":"I Gamvros","year":"2012","unstructured":"Gamvros I, Gouveia L, Raghavan S (2012) Reload cost trees and network design. Networks 59:365\u2013379","journal-title":"Networks"},{"issue":"2","key":"547_CR20","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1137\/0110022","volume":"10","author":"P Gilmore","year":"1962","unstructured":"Gilmore P (1962) Optimal and suboptimal algorithms for the quadratic assignment problem. J Soc Ind Appl Math 10(2):305\u2013313","journal-title":"J Soc Ind Appl Math"},{"issue":"4","key":"547_CR21","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1287\/mnsc.22.4.455","volume":"22","author":"F Glover","year":"1975","unstructured":"Glover F (1975) Improved linear integer programming formulations of nonlinear integer problems. Manag Sci 22(4):455\u2013460","journal-title":"Manag Sci"},{"issue":"13","key":"547_CR22","doi-asserted-by":"publisher","first-page":"1404","DOI":"10.1016\/j.dam.2010.03.009","volume":"158","author":"L Gourv\u00e8s","year":"2010","unstructured":"Gourv\u00e8s L, Lyra A, Martinhon C, Monnot J (2010) The minimum reload s-t path, trail and walk problems. Discrete Appl Math 158(13):1404\u20131417","journal-title":"Discrete Appl Math"},{"issue":"3","key":"547_CR23","doi-asserted-by":"publisher","first-page":"754","DOI":"10.1007\/s10878-017-0219-9","volume":"35","author":"H Hu","year":"2018","unstructured":"Hu H, Sotirov R (2018) Special cases of the quadratic shortest path problem. J Comb Optim 35(3):754\u2013777","journal-title":"J Comb Optim"},{"key":"547_CR24","unstructured":"Hu H, Sotirov R (2019) The linearization problem of binary quadratic problems and its applications. arXiv:1802.02426"},{"key":"547_CR25","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/978-3-540-85097-7_20","volume":"5165","author":"G J\u00e4ger","year":"2008","unstructured":"J\u00e4ger G, Molitor P (2008) Algorithms and experimental study for the traveling salesman of second order. Lect Notes Comput Sci 5165:211\u2013224","journal-title":"Lect Notes Comput Sci"},{"key":"547_CR26","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 $${\\cal{O}}(n^4)$$ algorithm for the QAP linearization problem. Math Oper Res 36:754\u2013761","journal-title":"Math Oper Res"},{"key":"547_CR27","doi-asserted-by":"publisher","first-page":"53","DOI":"10.2307\/1907742","volume":"25","author":"TC Koopmans","year":"1957","unstructured":"Koopmans TC, Beckmann MJ (1957) Assignment problems and the location of economic activities. Econometrica 25:53\u201376","journal-title":"Econometrica"},{"issue":"4","key":"547_CR28","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(4):586\u2013599","journal-title":"Manag Sci"},{"key":"547_CR29","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, \u0106usti\u0107, Punnen AP (2019) Combinatorial optimization problems with interaction costs: complexity and solvable cases. Discrete Optim 33:101\u2013117","journal-title":"Discrete Optim"},{"issue":"3","key":"547_CR30","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 Beckmann QAP linearization and related problems. Discrete Optim 10(3):200\u2013209","journal-title":"Discrete Optim"},{"key":"547_CR31","doi-asserted-by":"crossref","unstructured":"Punnen AP, Pandey P, Friesen M (2019) Representations of quadratic combinatorial optimization problems: a case study using quadratic set covering and quadratic knapsack problems. Comput Oper Res 112:104769","DOI":"10.1016\/j.cor.2019.104769"},{"key":"547_CR32","unstructured":"Punnen AP, Walter M, Woods BD (2018) A characterization of linearizable instances of the quadratic traveling salesman problem. arXiv: 1708.07217v3"},{"issue":"2","key":"547_CR33","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1016\/j.ejor.2018.01.054","volume":"268","author":"B Rostami","year":"2018","unstructured":"Rostami B, Chassein A, Hopf M, Frey D, Buchheim C, Malucelli F, Goerigk M (2018) The quadratic shortest path problem: complexity, approximability and solution methods. Eur J Oper Res 268(2):473\u2013485","journal-title":"Eur J Oper Res"},{"key":"547_CR34","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1016\/j.cor.2015.06.005","volume":"64","author":"B Rostami","year":"2015","unstructured":"Rostami B, Malucelli F (2015) Lower bounds for the quadratic minimum spanning tree problem based on reduced cost computation. Comput Oper Res 64:178\u2013188","journal-title":"Comput Oper Res"},{"key":"547_CR35","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1145\/321958.321975","volume":"23","author":"S Sahni","year":"1976","unstructured":"Sahni S, Gonzalez T (1976) P-complete approximation problems. J ACM 23:555\u2013565","journal-title":"J ACM"},{"key":"547_CR36","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.cor.2019.01.016","volume":"108","author":"R Stan\u011bk","year":"2019","unstructured":"Stan\u011bk R, Greistorfer P, Ladner K, Pferschy U (2019) Geometric and lp-based heuristics for angular travelling salesman problems in the plane. Comp Oper Res 108:97\u2013111","journal-title":"Comp Oper Res"},{"key":"547_CR37","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/S0166-218X(00)00392-9","volume":"113","author":"H Wirth","year":"2001","unstructured":"Wirth H, Steffan J (2001) Reload cost problems: minimum diameter spanning tree. Discrete Appl Math 113:73\u201385","journal-title":"Discrete Appl Math"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00547-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-020-00547-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00547-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,24]],"date-time":"2021-02-24T00:34:15Z","timestamp":1614126855000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-020-00547-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,25]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["547"],"URL":"https:\/\/doi.org\/10.1007\/s10878-020-00547-7","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2020,2,25]]},"assertion":[{"value":"25 February 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}