{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T17:22:40Z","timestamp":1762017760223},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,6,7]],"date-time":"2014-06-07T00:00:00Z","timestamp":1402099200000},"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":["Comput Optim Appl"],"published-print":{"date-parts":[[2015,1]]},"DOI":"10.1007\/s10589-014-9663-y","type":"journal-article","created":{"date-parts":[[2014,6,6]],"date-time":"2014-06-06T10:34:49Z","timestamp":1402050889000},"page":"171-198","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting"],"prefix":"10.1007","volume":"60","author":[{"given":"Jiming","family":"Peng","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tao","family":"Zhu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hezhi","family":"Luo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kim-Chuan","family":"Toh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,6,7]]},"reference":[{"key":"9663_CR1","first-page":"43","volume-title":"Quadratic Assignment and Related Problems. DIMACS Series in Discrete Mathematics and Theoretical Computer Science","author":"WP Adams","year":"1994","unstructured":"Adams, W.P., Johnson, T.A.: Improved linear programming-based lower bounds for the quadratic assignment problem. In: Pardalos, P.M., Wolkowicz, H. (eds.) Quadratic Assignment and Related Problems. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 16, pp. 43\u201375. AMS, Rhode Island (1994)"},{"key":"9663_CR2","doi-asserted-by":"crossref","first-page":"983","DOI":"10.1016\/j.ejor.2006.03.051","volume":"180","author":"W Adams","year":"2007","unstructured":"Adams, W., Guignard, M., Hahn, P., Hightower, W.: A level-2 reformulation-linearization technique bound for the quadratic assignment problem. Eur. J. Oper. Res. 180, 983\u2013996 (2007)","journal-title":"Eur. J. Oper. Res."},{"key":"9663_CR3","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/PL00011402","volume":"80","author":"K Anstreicher","year":"2001","unstructured":"Anstreicher, K., Brixius, N.: A new lower bound via projection for the quadratic assignment problem. Math. Program. 80, 341\u2013357 (2001)","journal-title":"Math. Program."},{"key":"9663_CR4","doi-asserted-by":"crossref","first-page":"2227","DOI":"10.1109\/TIT.2005.847750","volume":"51","author":"G Ben-David","year":"2005","unstructured":"Ben-David, G., Malah, D.: Bounds on the performance of vector-quantizers under channel errors. IEEE Trans. Inf. Theory 51, 2227\u20132235 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9663_CR5","doi-asserted-by":"crossref","first-page":"726","DOI":"10.1137\/040609574","volume":"16","author":"S Burer","year":"2006","unstructured":"Burer, S., Vandenbussche, D.: Solving lift-and-project relaxations of binary integer programs. SIAM J. Optim. 16, 726\u2013750 (2006)","journal-title":"SIAM J. Optim."},{"key":"9663_CR6","unstructured":"Burkard, R., Karisch, S., Rendl, F.: QAPLIB\u2014a quadratic assignment problem library. J. Glob. Optim. 10, 391\u2013403 (1997). Recent updates on QAPLIB are avaliable at http:\/\/www.seas.upenn.edu\/qaplib\/"},{"key":"9663_CR7","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898717754","volume-title":"Assignment Problems","author":"R Burkard","year":"2009","unstructured":"Burkard, R., Dell\u2019Amico, M., Martello, S.: Assignment Problems. Society for Industrial and Applied Mathematics, Philadelphia (2009)"},{"key":"9663_CR8","volume-title":"Das quadratische Zuweisungsproblem und zwei seiner Spezialfalle","author":"K Conrad","year":"1971","unstructured":"Conrad, K.: Das quadratische Zuweisungsproblem und zwei seiner Spezialfalle. Mohr Siebeck, Tubingen (1971)"},{"key":"9663_CR9","first-page":"11","volume":"83","author":"SA Carvalho de","year":"2006","unstructured":"de Carvalho, S.A., Rahmann, S.: Microarray layout as a quadratic assignment problem. Proc. Ger. Conf. Bioinform. 83, 11\u201320 (2006)","journal-title":"Proc. Ger. Conf. Bioinform."},{"key":"9663_CR10","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/s10107-008-0246-5","volume":"122","author":"E Klerk De","year":"2010","unstructured":"De Klerk, E., Sotirov, R.: Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem. Math. Program. 122, 225\u2013246 (2010)","journal-title":"Math. Program."},{"key":"9663_CR11","doi-asserted-by":"crossref","first-page":"1008","DOI":"10.1287\/moor.1090.0419","volume":"34","author":"Y Ding","year":"2009","unstructured":"Ding, Y., Wolkowicz, H.: A low-dimensional semidefinite relaxation for the quadratic assignment problem. Math. Oper. Res. 34, 1008\u20131022 (2009)","journal-title":"Math. Oper. Res."},{"key":"9663_CR12","first-page":"35","volume":"II","author":"C Edwards","year":"1980","unstructured":"Edwards, C.: A branch and bound algorithm for the Koopmans\u2013Beckmann quadratic assignment problem. Comb. Optim. II, 35\u201352 (1980)","journal-title":"Comb. Optim."},{"key":"9663_CR13","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0110022","volume":"10","author":"P Gilmore","year":"1962","unstructured":"Gilmore, P.: Optimal and suboptimal algorithms for the quadratic assignment problem. SIAM J. Appl. Math. 10, 305\u2013313 (1962)","journal-title":"SIAM J. Appl. Math."},{"key":"9663_CR14","unstructured":"Grant, M., Boyd, S., Ye, Y.: CVX: Matlab software for disciplined convex programming. http:\/\/www.stanford.edu\/boyd\/cvx . Accessed 2013"},{"key":"9663_CR15","doi-asserted-by":"crossref","first-page":"727","DOI":"10.1287\/moor.17.3.727","volume":"17","author":"SW Hadley","year":"1992","unstructured":"Hadley, S.W., Rendl, F., Wolkowicz, H.: A new lower bound via projection for the quadratic assignment problem. Math. Oper. Res. 17, 727\u2013739 (1992)","journal-title":"Math. Oper. Res."},{"key":"9663_CR16","unstructured":"Hahn, P., Grant, T.: Lower bounds for the quadratic assignment problem based upon a dual formulation. Oper. Res. 46, 912\u2013922 (1998)"},{"key":"9663_CR17","unstructured":"Hahn, P., Anjos, M., Burkard, R.E., Karisch, S.E., Rendl, F.: QAPLIB\u2014a quadratic assignment problem library. http:\/\/www.seas.upenn.edu\/qaplib\/ . Accessed 2013"},{"key":"9663_CR18","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1287\/ijoc.1110.0450","volume":"24","author":"PM Hahn","year":"2012","unstructured":"Hahn, P.M., Zhu, Y.R., Guignard, M., Hightower, W.L., Saltzman, M.J.: A level-3 reformulation-linearization technique-based bound for the quadratic assignment problem. INFORMS J. Comput. 24, 202\u2013209 (2012)","journal-title":"INFORMS J. Comput."},{"key":"9663_CR19","first-page":"213","volume":"1","author":"M Hanan","year":"1972","unstructured":"Hanan, M., Kurtzberg, J.: Placement techniques. Des. Autom. Digital Syst. 1, 213\u2013282 (1972)","journal-title":"Des. Autom. Digital Syst."},{"key":"9663_CR20","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511810817","volume-title":"Matrix Analysis","author":"RA Horn","year":"1985","unstructured":"Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1985)"},{"key":"9663_CR21","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1137\/050622870","volume":"46","author":"C Jansson","year":"2007","unstructured":"Jansson, C., Chaykin, D., Keil, C.: Rigorous error bounds for the optimal value in semidefinite programming. SIAM J. Numer. Anal. 46, 180\u2013200 (2007)","journal-title":"SIAM J. Numer. Anal."},{"key":"9663_CR22","doi-asserted-by":"crossref","first-page":"53","DOI":"10.2307\/1907742","volume":"25","author":"T Koopmans","year":"1957","unstructured":"Koopmans, T., Beckmann, M.: Assignment problems and the location of economic activities. Econometrica 25, 53\u201376 (1957)","journal-title":"Econometrica"},{"key":"9663_CR23","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1287\/mnsc.9.4.586","volume":"9","author":"E Lawler","year":"1963","unstructured":"Lawler, E.: The quadratic assignment problem. Manage. Sci. 9, 589\u2013599 (1963)","journal-title":"Manage. Sci."},{"key":"9663_CR24","doi-asserted-by":"crossref","first-page":"657","DOI":"10.1016\/j.ejor.2005.09.032","volume":"176","author":"E Loiola","year":"2007","unstructured":"Loiola, E., Abreu, N., Boaventura-Netto, P., Hahn, P., Querido, T.: A survey for the quadratic assignment problem. Eur. J. Oper. Res. 176, 657\u2013690 (2007)","journal-title":"Eur. J. Oper. Res."},{"key":"9663_CR25","doi-asserted-by":"crossref","first-page":"3408","DOI":"10.1137\/090748834","volume":"20","author":"H Mittelmann","year":"2010","unstructured":"Mittelmann, H., Peng, J.: Estimating bounds for quadratic assignment problems associated with Hamming and Manhattan distance matrices based on semidefinite programming. SIAM J. Optim. 20, 3408\u20133426 (2010)","journal-title":"SIAM J. Optim."},{"key":"9663_CR26","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/s10878-008-9184-7","volume":"17","author":"L Mukherjee","year":"2009","unstructured":"Mukherjee, L., Singh, V., Peng, J., Xu, J., Zeitz, M., Berezney, R.: Generalized median graphs and applications. J Combin. Optim. 17, 21\u201344 (2009)","journal-title":"J Combin. Optim."},{"key":"9663_CR27","doi-asserted-by":"crossref","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, 59\u201377 (2010)","journal-title":"Math. Program. Comput."},{"key":"9663_CR28","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1007\/s10107-006-0038-8","volume":"109","author":"F Rendl","year":"2007","unstructured":"Rendl, F., Sotirov, R.: Bounds for the quadratic assignment problem using the bundle method. Math. Program. 109, 505\u2013524 (2007)","journal-title":"Math. Program."},{"key":"9663_CR29","first-page":"185","volume":"32","author":"C Roucairol","year":"1979","unstructured":"Roucairol, C.: A reduction method for quadratic assignment problems. Methods Oper. Res. 32, 185\u2013187 (1979)","journal-title":"Methods Oper. Res."},{"key":"9663_CR30","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0966-8349(95)00008-6","volume":"3","author":"E Taillard","year":"1995","unstructured":"Taillard, E.: Comparison of iterative searches for the quadratic assignment problem. Locat. Sci. 3, 87\u2013105 (1995)","journal-title":"Locat. Sci."},{"key":"9663_CR31","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1017\/S0305004100051070","volume":"77","author":"CM Theobald","year":"1975","unstructured":"Theobald, C.M.: An inequality for the trace of the product of two symmetric matrices. Math. Proc. Camb. Philos. Soc. 77, 77\u2013265 (1975)","journal-title":"Math. Proc. Camb. Philos. Soc."},{"key":"9663_CR32","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1080\/10556789908805762","volume":"11","author":"K Toh","year":"1999","unstructured":"Toh, K., Todd, M., Tutuncu, R.: SDPT3: Matlab software package for semidefinite programming. Optim. Methods Softw. 11, 545\u2013581 (1999)","journal-title":"Optim. Methods Softw."},{"key":"9663_CR33","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1023\/A:1009795911987","volume":"2","author":"Q Zhao","year":"1998","unstructured":"Zhao, Q., Karisch, S., Rendl, F., Wolkowicz, H.: Semidefinite programming relaxations for the quadratic assignment problem. J. Combin. Optim. 2, 71\u2013109 (1998)","journal-title":"J. Combin. Optim."},{"key":"9663_CR34","doi-asserted-by":"crossref","first-page":"1737","DOI":"10.1137\/080718206","volume":"20","author":"X Zhao","year":"2010","unstructured":"Zhao, X., Sun, D., Toh, K.: A Newton-CG augmented Lagrangian method for semidefinite programming. SIAM J. Optim. 20, 1737\u20131765 (2010)","journal-title":"SIAM J. Optim."}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-014-9663-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10589-014-9663-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-014-9663-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T18:37:36Z","timestamp":1559241456000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10589-014-9663-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6,7]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["9663"],"URL":"https:\/\/doi.org\/10.1007\/s10589-014-9663-y","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,6,7]]}}}