{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T03:54:07Z","timestamp":1777694047343,"version":"3.51.4"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2017,1,19]],"date-time":"2017-01-19T00:00:00Z","timestamp":1484784000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2017,11]]},"DOI":"10.1007\/s10107-017-1111-1","type":"journal-article","created":{"date-parts":[[2017,1,19]],"date-time":"2017-01-19T20:41:38Z","timestamp":1484858498000},"page":"185-205","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["The bilinear assignment problem: complexity and polynomially solvable special cases"],"prefix":"10.1007","volume":"166","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4616-2932","authenticated-orcid":false,"given":"Ante","family":"\u0106usti\u0107","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vladyslav","family":"Sokol","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abraham P.","family":"Punnen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Binay","family":"Bhattacharya","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,1,19]]},"reference":[{"key":"1111_CR1","unstructured":"Ahuja, R.K., Ergun, O., Orlin, J.B., Punnen, A.P.: Very large scale neighborhood search: theory, algorithms and applications, approximation algorithms and metaheuristics. In: Gonzalez, T.F. (ed.): Handbook of approximation algorithms and metaheuristics. CRC Press (2007)"},{"key":"1111_CR2","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1016\/j.jalgor.2003.09.003","volume":"50","author":"N Alon","year":"2004","unstructured":"Alon, N., Gutin, G., Krivelevich, M.: Algorithms with large domination ratio. J. Algorithms 50, 118\u2013131 (2004)","journal-title":"J. Algorithms"},{"key":"1111_CR3","first-page":"741","volume":"16","author":"M Altman","year":"1968","unstructured":"Altman, M.: Bilinear programming. Bull. de l\u2019 Acad\u00e9mie Pol. des Sci. 16, 741\u2013746 (1968)","journal-title":"Bull. de l\u2019 Acad\u00e9mie Pol. des Sci."},{"key":"1111_CR4","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/S0166-218X(97)00129-7","volume":"82","author":"E Angel","year":"1995","unstructured":"Angel, E., Zissimopoulos, V.: On the quality of local search for the quadratic assignment problem. Discrete Appl. Math. 82, 15\u201325 (1995)","journal-title":"Discrete Appl. Math."},{"key":"1111_CR5","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1016\/0377-2217(79)90143-7","volume":"3","author":"X Berenguer","year":"1979","unstructured":"Berenguer, X.: A characterization of linear admissible transformations for the \n                        $$m$$\n                        \n                            \n                                            \n                                m\n                            \n                        \n                    -traveling salesman problem. Eur. J. Op. Res. 3, 232\u2013238 (1979)","journal-title":"Eur. J. Op. Res."},{"key":"1111_CR6","first-page":"125","volume":"82","author":"RE Burkard","year":"1998","unstructured":"Burkard, R.E., \u00c7ela, E., Rote, G., Woeginger, G.J.: The quadratic assignment problem with monotone anti-Monge and symmetric Toeplitz matrix: easy and hard cases. Math. Program. 82, 125\u2013158 (1998)","journal-title":"Math. Program."},{"key":"1111_CR7","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898717754","volume-title":"Assignment Problems","author":"RE Burkard","year":"2009","unstructured":"Burkard, R.E., Dell\u2019Amico, M., Martello, S.: Assignment Problems. SIAM, Philadelphia (2009)"},{"key":"1111_CR8","doi-asserted-by":"crossref","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.: The Quadratic Assignment Problem: Theory and Algorithms. Kluwer Academic Publishers, Dordrecht (1998)"},{"key":"1111_CR9","doi-asserted-by":"crossref","first-page":"1269","DOI":"10.1007\/s10878-014-9821-2","volume":"31","author":"E \u00c7ela","year":"2016","unstructured":"\u00c7ela, E., De\u012dneko, V.G., Woeginger, G.J.: Linearizable special cases of the QAP. J. Comb. Optim. 31, 1269\u20131279 (2016)","journal-title":"J. Comb. Optim."},{"key":"1111_CR10","doi-asserted-by":"crossref","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.: The constant objective value property for multidimensional assignment problems. Discrete Optim. 19, 23\u201335 (2016)","journal-title":"Discrete Optim."},{"key":"1111_CR11","unstructured":"\u0106usti\u0107, A., Punnen, A.P.: Average value of solutions of the bipartite quadratic assignment problem and linkages to domination analysis. \n                        arXiv:1512.02709\n                        \n                     (2015)"},{"key":"1111_CR12","unstructured":"\u0106usti\u0107, A., Punnen, A.P.: Characterization of the linearizable instances of the quadratic minimum spanning tree problem. \n                        arXiv:1510.02197\n                        \n                     (2015)"},{"key":"1111_CR13","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1007\/s101070050010","volume":"87","author":"VG De\u012dneko","year":"2000","unstructured":"De\u012dneko, V.G., Woeginger, G.J.: A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem. Math. Program. 87, 519\u2013542 (2000)","journal-title":"Math. Program."},{"key":"1111_CR14","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/S0012-365X(97)89167-4","volume":"171","author":"D Fon-Der-Flaass","year":"1997","unstructured":"Fon-Der-Flaass, D.: Arrays of distinct representatives\u2014a very simple NP-complete problem. Discrete Math. 171, 295\u2013298 (1997)","journal-title":"Discrete Math."},{"key":"1111_CR15","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0377-2217(83)90078-4","volume":"13","author":"AM Frieze","year":"1983","unstructured":"Frieze, A.M.: Complexity of a 3-dimensional assignment problem. Eur. J. Op. Res. 13, 161\u2013164 (1983)","journal-title":"Eur. J. Op. Res."},{"key":"1111_CR16","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1007\/BF01585532","volume":"7","author":"AM Frieze","year":"1974","unstructured":"Frieze, A.M.: A bilinear programming formulation of the 3-dimensional assignment problem. Math. Program. 7, 376\u2013379 (1974)","journal-title":"Math. Program."},{"key":"1111_CR17","doi-asserted-by":"crossref","first-page":"502","DOI":"10.1057\/palgrave.jors.2600392","volume":"48","author":"F Glover","year":"1997","unstructured":"Glover, F., Punnen, A.P.: The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms. J. Op. Res. Soc. 48, 502\u2013510 (1997)","journal-title":"J. Op. Res. Soc."},{"key":"1111_CR18","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1287\/mnsc.16.7.453","volume":"16","author":"GW Graves","year":"1970","unstructured":"Graves, G.W., Whinston, A.B.: An algorithm for the quadratic assignment problem. Manag. Sci. 16, 453\u2013471 (1970)","journal-title":"Manag. Sci."},{"key":"1111_CR19","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0167-6377(92)90049-9","volume":"12","author":"LK Grover","year":"1992","unstructured":"Grover, L.K.: Local search and the local structure of NP-complete problems. Op. Res. Lett. 12, 235\u2013243 (1992)","journal-title":"Op. Res. Lett."},{"key":"1111_CR20","doi-asserted-by":"crossref","first-page":"2613","DOI":"10.1016\/j.dam.2006.02.010","volume":"154","author":"G Gutin","year":"2006","unstructured":"Gutin, G., Jensen, T., Yeo, A.: Domination analysis for minimum multiprocessor scheduling. Discrete Appl. Math. 154, 2613\u20132619 (2006)","journal-title":"Discrete Appl. Math."},{"key":"1111_CR21","doi-asserted-by":"crossref","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.: Domination analysis of combinatorial optimization problems. Discrete Appl. Math. 129, 513\u2013520 (2003)","journal-title":"Discrete Appl. Math."},{"key":"1111_CR22","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/S0166-218X(01)00267-0","volume":"119","author":"G Gutin","year":"2002","unstructured":"Gutin, G., Yeo, A.: Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number. Discrete Appl. Math. 119, 107\u2013116 (2002)","journal-title":"Discrete Appl. Math."},{"key":"1111_CR23","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/S0167-6377(01)00053-0","volume":"28","author":"G Gutin","year":"2001","unstructured":"Gutin, G., Yeo, A.: TSP tour domination and Hamilton cycle decompositions of regular graphs. Op. Res. Lett. 28, 107\u2013111 (2001)","journal-title":"Op. Res. Lett."},{"key":"1111_CR24","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1006\/jagm.2001.1187","volume":"41","author":"R Hassin","year":"2001","unstructured":"Hassin, R., Khuller, S.: z-Approximations. J. Algorithms 41, 429\u2013442 (2001)","journal-title":"J. Algorithms"},{"key":"1111_CR25","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/BF01580380","volume":"11","author":"H Konno","year":"1976","unstructured":"Konno, H.: Maximization of a convex quadratic function under linear constraints. Math. Program. 11, 117\u2013127 (1976)","journal-title":"Math. Program."},{"key":"1111_CR26","doi-asserted-by":"crossref","first-page":"754","DOI":"10.1287\/moor.1110.0509","volume":"36","author":"SN Kabadi","year":"2011","unstructured":"Kabadi, S.N., Punnen, A.P.: An \n                        $$O(n^4)$$\n                        \n                            \n                                            \n                                \n                                    O\n                                    (\n                                    \n                                        n\n                                        4\n                                    \n                                    )\n                                \n                            \n                        \n                     algorithm for the QAP linearization problem. Math. Op. Res. 36, 754\u2013761 (2011)","journal-title":"Math. Op. Res."},{"key":"1111_CR27","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/j.aim.2013.01.005","volume":"237","author":"D Kuhn","year":"2013","unstructured":"Kuhn, D., Osthus, D.: Hamilton decompositions of regular expanders: a proof of Kelly\u2019s conjecture for large tournaments. Adv. Math. 237, 62\u2013146 (2013)","journal-title":"Adv. Math."},{"key":"1111_CR28","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1016\/j.disc.2003.05.008","volume":"275","author":"AE Koller","year":"2004","unstructured":"Koller, A.E., Noble, S.D.: Domination analysis of greedy heuristics for the frequency assignment problem. Discrete Math. 275, 331\u2013338 (2004)","journal-title":"Discrete Math."},{"key":"1111_CR29","doi-asserted-by":"crossref","first-page":"370","DOI":"10.1016\/j.disopt.2009.04.004","volume":"6","author":"A Mitrovi\u0107-Mini\u0107","year":"2009","unstructured":"Mitrovi\u0107-Mini\u0107, A., Punnen, A.P.: Local search intensified: very large-scale variable neighborhood search for the multi-resource generalized assignment problem. Discrete Optim. 6, 370\u2013377 (2009)","journal-title":"Discrete Optim."},{"key":"1111_CR30","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1007\/s10107-011-0511-x","volume":"141","author":"S Mittal","year":"2012","unstructured":"Mittal, S., Schulz, A.S.: An FPTAS for optimizing a class of low-rank functions over a polytope. Math. Program. 141, 103\u2013120 (2012)","journal-title":"Math. Program."},{"key":"1111_CR31","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/S0166-218X(01)00268-2","volume":"119","author":"AP Punnen","year":"2002","unstructured":"Punnen, A.P., Kabadi, S.N.: Domination analysis of some heuristics for the asymmetric traveling salesman problem. Discrete Appl. Math. 119, 117\u2013128 (2002)","journal-title":"Discrete Appl. Math."},{"key":"1111_CR32","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/s00453-002-0986-1","volume":"35","author":"AP Punnen","year":"2003","unstructured":"Punnen, A.P., Margot, F., Kabadi, S.N.: TSP heuristics: domination analysis and complexity. Algorithmica 35, 111\u2013127 (2003)","journal-title":"Algorithmica"},{"key":"1111_CR33","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1016\/j.disopt.2013.02.003","volume":"10","author":"AP Punnen","year":"2013","unstructured":"Punnen, A.P., Kabadi, S.N.: A linear time algorithm for the Koopmans-Beckman QAP linearization and related problems. Discrete Optim. 10, 200\u2013209 (2013)","journal-title":"Discrete Optim."},{"key":"1111_CR34","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/j.tcs.2014.11.008","volume":"565","author":"AP Punnen","year":"2015","unstructured":"Punnen, A.P., Sripratak, P., Karapetyan, D.: Average value of solutions for the bipartite boolean quadratic programs and rounding algorithms. Theor. Comput. Sci. 565, 77\u201389 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"1111_CR35","first-page":"18","volume":"4","author":"VI Rublineckii","year":"1973","unstructured":"Rublineckii, V.I.: Estimates of the accuracy of procedures in the traveling salesman problem. Numer. Math. Comput. Technol. 4, 18\u201323 (1973). (in Russian)","journal-title":"Numer. Math. Comput. Technol."},{"key":"1111_CR36","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1145\/321958.321975","volume":"23","author":"S Sahni","year":"1976","unstructured":"Sahni, S., Gonzalez, T.F.: P-complete approximation problems. J. ACM 23, 555\u2013565 (1976)","journal-title":"J. ACM"},{"key":"1111_CR37","first-page":"8","volume":"31","author":"V Sarvanov","year":"1981","unstructured":"Sarvanov, V., Doroshko, N.: The approximate solution of the traveling salesman problem by a local algorithm that searches neighborhoods of exponential cardinality in quadratic time. Softw. Algorithms Progr. 31, 8\u201311 (1981). (in Russian)","journal-title":"Softw. Algorithms Progr."},{"key":"1111_CR38","first-page":"11","volume":"31","author":"V Sarvanov","year":"1981","unstructured":"Sarvanov, V., Doroshko, N.: The approximate solution of the traveling salesman problem by a local algorithm that searches neighborhoods of factorial cardinality in cubic time. Softw. Algorithms Progr. 31, 11\u201313 (1981). (in Russian)","journal-title":"Softw. Algorithms Progr."},{"key":"1111_CR39","first-page":"51","volume":"139","author":"V Sarvanov","year":"1978","unstructured":"Sarvanov, V.: The mean value of the functional in sampling problems, Vestsi Akademii Navuk BSSR. Ser. Fiz. Mat. Navuk 139, 51\u201354 (1978)","journal-title":"Ser. Fiz. Mat. Navuk"},{"key":"1111_CR40","volume-title":"Multi Index Assignment Problems: Complexity, Approximation, Applications, Nonlinear Assignment Problems, 1\u201312","author":"FCR Spieksma","year":"2000","unstructured":"Spieksma, F.C.R.: Multi Index Assignment Problems: Complexity, Approximation, Applications, Nonlinear Assignment Problems, 1\u201312. Kluwer Academic Publishers, Dordrecht (2000)"},{"key":"1111_CR41","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/0041-5553(81)90142-7","volume":"21","author":"SP Tarasov","year":"1981","unstructured":"Tarasov, S.P.: Properties of the trajectories of the appointments problem and the travelling-salesman problem. USSR Comput. Math. Math. Phys. 21, 167\u2013174 (1981)","journal-title":"USSR Comput. Math. Math. Phys."},{"key":"1111_CR42","doi-asserted-by":"crossref","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.: A low-rank bilinear programming approach for sub-optimal solution of the quadratic assignment problem. Eur. J. Op. Res. 94, 384\u2013391 (1996)","journal-title":"Eur. J. Op. Res."},{"key":"1111_CR43","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0360-8352(90)90128-9","volume":"19","author":"LY Tsui","year":"1990","unstructured":"Tsui, L.Y., Chang, C.-H.: A microcomputer based decision support tool for assigning dock doors in freight yards. Comput. Ind. Eng. 19, 309\u2013312 (1990)","journal-title":"Comput. Ind. Eng."},{"key":"1111_CR44","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/0360-8352(92)90117-3","volume":"23","author":"LY Tsui","year":"1992","unstructured":"Tsui, L.Y., Chang, C.-H.: An optimal solution to a dock door assignment problem. Comput. Ind. Eng. 23, 283\u2013286 (1992)","journal-title":"Comput. Ind. Eng."},{"key":"1111_CR45","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1016\/j.disopt.2007.11.009","volume":"5","author":"Y Twitto","year":"2008","unstructured":"Twitto, Y.: Dominance guarantees for above-average solutions. Discrete Optim. 5, 563\u2013568 (2008)","journal-title":"Discrete Optim."},{"key":"1111_CR46","first-page":"76","volume":"5","author":"VG Vizing","year":"1973","unstructured":"Vizing, V.G.: Values of the target functional in a priority problem that are majorized by the mean value. Kibernetika 5, 76\u201378 (1973)","journal-title":"Kibernetika"},{"key":"1111_CR47","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1287\/moor.6.3.319","volume":"6","author":"E Zemel","year":"1981","unstructured":"Zemel, E.: Measuring the quality of approximate solutions to zero-one programming problems. Math. Op. Res. 6, 319\u2013332 (1981)","journal-title":"Math. Op. Res."},{"key":"1111_CR48","unstructured":"Zikan, K.: Track Initialization in the Multiple-Object Tracking Problem, Technical Report SOL-88-18, Systems Optimization Laboratory. Stanford University, California. \n                        http:\/\/www.dtic.mil\/dtic\/tr\/fulltext\/u2\/a202284.pdf\n                        \n                     (1988)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-017-1111-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-017-1111-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-017-1111-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,10,13]],"date-time":"2017-10-13T04:30:43Z","timestamp":1507869043000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-017-1111-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1,19]]},"references-count":48,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2017,11]]}},"alternative-id":["1111"],"URL":"https:\/\/doi.org\/10.1007\/s10107-017-1111-1","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1,19]]}}}