{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T04:06:08Z","timestamp":1751601968109,"version":"3.41.0"},"reference-count":34,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T00:00:00Z","timestamp":1764547200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T00:00:00Z","timestamp":1764547200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"am","delay-in-days":212,"URL":"http:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"},{"start":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T00:00:00Z","timestamp":1764547200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T00:00:00Z","timestamp":1764547200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T00:00:00Z","timestamp":1764547200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T00:00:00Z","timestamp":1764547200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T00:00:00Z","timestamp":1764547200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2025,12]]},"DOI":"10.1016\/j.dam.2025.06.035","type":"journal-article","created":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T16:29:19Z","timestamp":1751387359000},"page":"281-293","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["A polyhedral characterization of linearizable quadratic combinatorial optimization problems"],"prefix":"10.1016","volume":"376","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1781-4049","authenticated-orcid":false,"given":"Lucas A.","family":"Waddell","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"issue":"3","key":"10.1016\/j.dam.2025.06.035_b1","doi-asserted-by":"crossref","first-page":"983","DOI":"10.1016\/j.ejor.2006.03.051","article-title":"A level-2 reformulation-linearization technique bound for the quadratic assignment problem","volume":"180","author":"Adams","year":"2007","journal-title":"European J. Oper. Res."},{"key":"10.1016\/j.dam.2025.06.035_b2","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1090\/dimacs\/016\/02","article-title":"Improved linear programming-based lower bounds for the quadratic assignment problem","volume":"16","author":"Adams","year":"1994","journal-title":"DIMACS Ser. Discrete Math. Theoret. Comput. Sci."},{"key":"10.1016\/j.dam.2025.06.035_b3","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1016\/j.disopt.2014.07.001","article-title":"Linear programming insights into solvable cases of the quadratic assignment problem","volume":"14","author":"Adams","year":"2014","journal-title":"Discrete Optim."},{"issue":"3","key":"10.1016\/j.dam.2025.06.035_b4","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1007\/s101070100255","article-title":"Solving large quadratic assignment problems on computational grids","volume":"91","author":"Anstreicher","year":"2002","journal-title":"Math. Program."},{"key":"10.1016\/j.dam.2025.06.035_b5","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1002\/1520-6750(199204)39:3<399::AID-NAV3220390309>3.0.CO;2-0","article-title":"The quadratic minimum spanning tree problem","volume":"39","author":"Assad","year":"1992","journal-title":"Naval Res. Logist."},{"year":"2004","series-title":"Convex Optimization","author":"Boyd","key":"10.1016\/j.dam.2025.06.035_b6"},{"year":"1997","series-title":"Perspectives of Easy and Hard Cases of the Quadratic Assignment Problem","author":"Burkard","key":"10.1016\/j.dam.2025.06.035_b7"},{"issue":"1\u20132","key":"10.1016\/j.dam.2025.06.035_b8","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/BF01585868","article-title":"The quadratic assignment problem with a monotone anti-Monge matrix and a symmetric Toeplitz matrix: easy and hard cases","volume":"82","author":"Burkard","year":"1998","journal-title":"Math. Program."},{"year":"1998","series-title":"The Quadratic Assignment Problem: Theory and Algorithms","author":"\u00c7ela","key":"10.1016\/j.dam.2025.06.035_b9"},{"issue":"6","key":"10.1016\/j.dam.2025.06.035_b10","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1016\/j.orl.2012.06.005","article-title":"Another well-solvable case of the QAP: Maximizing the job completion time variance","volume":"40","author":"\u00c7ela","year":"2012","journal-title":"Oper. Res. Lett."},{"key":"10.1016\/j.dam.2025.06.035_b11","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/j.dam.2015.01.005","article-title":"Well-solvable cases of the QAP with block-structured matrices","volume":"186","author":"\u00c7ela","year":"2015","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"10.1016\/j.dam.2025.06.035_b12","doi-asserted-by":"crossref","first-page":"1269","DOI":"10.1007\/s10878-014-9821-2","article-title":"Linearizable special cases of the QAP","volume":"31","author":"\u00c7ela","year":"2016","journal-title":"J. Comb. Optim."},{"key":"10.1016\/j.dam.2025.06.035_b13","series-title":"Graph-Theoretic Concepts in Computer Science","first-page":"245","article-title":"Linearizable special cases of the quadratic shortest path problem","author":"\u00c7ela","year":"2021"},{"key":"10.1016\/j.dam.2025.06.035_b14","article-title":"A linear time algorithm for linearizing quadratic and higher-order shortest path problems","author":"\u00c7ela","year":"2024","journal-title":"Math. Program. Ser. B, Open Access"},{"issue":"3","key":"10.1016\/j.dam.2025.06.035_b15","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1016\/j.disopt.2011.02.002","article-title":"The Wiener maximum quadratic assignment problem","volume":"8","author":"\u00c7ela","year":"2011","journal-title":"Discrete Optim."},{"key":"10.1016\/j.dam.2025.06.035_b16","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1007\/s10878-017-0184-3","article-title":"A characterization of linearizable instances of the quadratic minimum spanning tree problem","volume":"35","author":"\u0106usti\u0107","year":"2018","journal-title":"J. Comb. Optim."},{"key":"10.1016\/j.dam.2025.06.035_b17","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/s10107-017-1111-1","article-title":"The bilinear assignment problem: complexity and polynomially solvable special cases","volume":"166","author":"\u0106usti\u0107","year":"2017","journal-title":"Math. Program."},{"key":"10.1016\/j.dam.2025.06.035_b18","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/j.disopt.2017.09.003","article-title":"The quadratic minimum spanning tree problem and its variations","volume":"27","author":"\u0106usti\u0107","year":"2018","journal-title":"Discrete Optim."},{"issue":"1","key":"10.1016\/j.dam.2025.06.035_b19","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/S0167-6377(97)00047-3","article-title":"A solvable case of the quadratic assignment problem","volume":"22","author":"Deineko","year":"1998","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"10.1016\/j.dam.2025.06.035_b20","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1016\/j.disopt.2006.04.001","article-title":"A note on a polynomial time solvable case of the quadratic assignment problem","volume":"3","author":"Erdo\u011fan","year":"2006","journal-title":"Discrete Optim."},{"issue":"4","key":"10.1016\/j.dam.2025.06.035_b21","doi-asserted-by":"crossref","first-page":"676","DOI":"10.1287\/ijoc.2017.0754","article-title":"A graphics processing unit algorithm to solve the quadratic assignment problem using level-2 reformulation-linearization technique","volume":"29","author":"Gon\u00e7alves","year":"2017","journal-title":"INFORMS J. Comput."},{"issue":"5\u20136","key":"10.1016\/j.dam.2025.06.035_b22","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1023\/A:1012252420779","article-title":"A hospital facility problem finally solved","volume":"12","author":"Hahn","year":"2001","journal-title":"J. Intell. Manuf."},{"issue":"2","key":"10.1016\/j.dam.2025.06.035_b23","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1287\/ijoc.1110.0450","article-title":"A level-3 reformulation-linearization technique bound for the quadratic assignment problem","volume":"24","author":"Hahn","year":"2012","journal-title":"INFORMS J. Comput."},{"key":"10.1016\/j.dam.2025.06.035_b24","doi-asserted-by":"crossref","first-page":"754","DOI":"10.1007\/s10878-017-0219-9","article-title":"Special cases of the quadratic shortest path problem","volume":"35","author":"Hu","year":"2018","journal-title":"J. Comb. Optim."},{"issue":"4","key":"10.1016\/j.dam.2025.06.035_b25","doi-asserted-by":"crossref","first-page":"754","DOI":"10.1287\/moor.1110.0509","article-title":"An O(n4) algorithm for the QAP linearization problem","volume":"36","author":"Kabadi","year":"2011","journal-title":"Math. Oper. Res."},{"year":"2012","series-title":"Combinatorial Optimization: Theory and Algorithms","author":"Korte","key":"10.1016\/j.dam.2025.06.035_b26"},{"issue":"1","key":"10.1016\/j.dam.2025.06.035_b27","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/j.orl.2014.12.009","article-title":"The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure","volume":"43","author":"Laurent","year":"2015","journal-title":"Oper. Res. Lett."},{"key":"10.1016\/j.dam.2025.06.035_b28","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/j.cor.2015.04.020","article-title":"Lower bounds and exact algorithms for the quadratic minimum spanning tree problem","volume":"63","author":"Pereira","year":"2015","journal-title":"Comput. Oper. Res."},{"issue":"3","key":"10.1016\/j.dam.2025.06.035_b29","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1016\/j.disopt.2013.02.003","article-title":"A linear time algorithm for the koopmans-beckmann QAP linearization and related problems","volume":"10","author":"Punnen","year":"2013","journal-title":"Discrete Optim."},{"key":"10.1016\/j.dam.2025.06.035_b30","article-title":"Representations of quadratic combinatorial optimization problems: a case study using quadratic set covering and quadratic knapsack problems","volume":"122","author":"Punnen","year":"2019","journal-title":"Comput. Oper. Res."},{"issue":"2","key":"10.1016\/j.dam.2025.06.035_b31","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1016\/j.ejor.2018.01.054","article-title":"The quadratic shortest path problem: complexity, approximability, and solution methods","volume":"268","author":"Rostami","year":"2018","journal-title":"European J. Oper. Res."},{"issue":"9","key":"10.1016\/j.dam.2025.06.035_b32","doi-asserted-by":"crossref","first-page":"572","DOI":"10.1109\/TCS.1976.1084251","article-title":"On the incidence matrix of a graph","volume":"23","author":"Van Nuffelen","year":"1976","journal-title":"IEEE Trans. Circuits Syst."},{"key":"10.1016\/j.dam.2025.06.035_b33","doi-asserted-by":"crossref","DOI":"10.1016\/j.disopt.2023.100812","article-title":"Characterizing linearizable QAPs by the level-1 reformulation-linearization technique","volume":"51","author":"Waddell","year":"2024","journal-title":"Discrete Optim."},{"issue":"114","key":"10.1016\/j.dam.2025.06.035_b34","article-title":"An LP-based characterization of solvable QAP instances with chess-board and graded structures","volume":"45","author":"Waddell","year":"2023","journal-title":"J. Comb. Optim."}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X25003373?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X25003373?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T12:20:24Z","timestamp":1751545224000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X25003373"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12]]},"references-count":34,"alternative-id":["S0166218X25003373"],"URL":"https:\/\/doi.org\/10.1016\/j.dam.2025.06.035","relation":{},"ISSN":["0166-218X"],"issn-type":[{"type":"print","value":"0166-218X"}],"subject":[],"published":{"date-parts":[[2025,12]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"A polyhedral characterization of linearizable quadratic combinatorial optimization problems","name":"articletitle","label":"Article Title"},{"value":"Discrete Applied Mathematics","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.dam.2025.06.035","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2025 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.","name":"copyright","label":"Copyright"}]}}