{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,19]],"date-time":"2026-08-19T06:13:08Z","timestamp":1787119988682,"version":"3.56.0"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1998,3,1]],"date-time":"1998-03-01T00:00:00Z","timestamp":888710400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1998,3,1]],"date-time":"1998-03-01T00:00:00Z","timestamp":888710400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Combinatorial Optimization"],"published-print":{"date-parts":[[1998,3]]},"DOI":"10.1023\/a:1009795911987","type":"journal-article","created":{"date-parts":[[2002,12,22]],"date-time":"2002-12-22T22:50:41Z","timestamp":1040597441000},"page":"71-109","source":"Crossref","is-referenced-by-count":157,"title":["Semidefinite Programming Relaxations for the Quadratic Assignment Problem"],"prefix":"10.1007","volume":"2","author":[{"given":"Qing","family":"Zhao","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefan E.","family":"Karisch","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Franz","family":"Rendl","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Henry","family":"Wolkowicz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"157589_CR1","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1090\/dimacs\/016\/02","volume":"16","author":"W.P. Adams","year":"1994","unstructured":"W.P. Adams and T.A. Johnson, \u201cImproved linear programming-based lower bounds for the quadratic assignment problem,\u201d in Proceedings of the DIMACS Workshop on Quadratic Assignment Problems, volume 16 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, 1994, pp. 43-75.","journal-title":"Proceedings of the DIMACS Workshop on Quadratic Assignment Problems"},{"key":"157589_CR2","series-title":"Technical report","first-page":"113","volume-title":"SIMA","author":"F. Alizadeh","year":"1994","unstructured":"F. Alizadeh, J-P.A. Haeberly, and M.L. Overton, \u201cA new primal-dual interior-point method for semidefinite programming,\u201d Technical report, Courant Institute of Mathematical Sciences, 1994, in Proceedings of the Fifth SIAM Conference on Applied Linear Algebra, J.G. Lewis (Ed.), SIMA, Snowbird, Utah, June 1994, pp. 113-117."},{"key":"157589_CR3","doi-asserted-by":"crossref","first-page":"15","DOI":"10.2140\/pjm.1975.57.15","volume":"57","author":"G.P. Barker","year":"1975","unstructured":"G.P. Barker and D. Carlson, \u201cCones of diagonally dominant matrices,\u201d Pacific J. of Math., vol. 57, pp. 15-32, 1975.","journal-title":"Pacific J. of Math."},{"key":"157589_CR4","volume-title":"Studies in Applied Mathematics","author":"S. Boyd","year":"1994","unstructured":"S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan, Linear Matrix Inequalities in System and Control Theory, volume 15 of Studies in Applied Mathematics, SIAM: Philadelphia, PA, June 1994."},{"key":"157589_CR5","unstructured":"R.E. Burkard, \u201cLocations with spatial interactions: The quadratic assignment problem,\u201d in Discrete Location Theory, P.B. Mirchandani and R.L. Francis (Eds.), John Wiley, 1991."},{"key":"157589_CR6","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/0377-2217(91)90197-4","volume":"55","author":"R.E. Burkard","year":"1991","unstructured":"R.E. Burkard, S. Karisch, and F. Rendl, \u201cAquadratic assignment problem library,\u201d European Journal of Operations Research, vol. 55, pp. 151-119, 1991. http:\/\/fmatbhp1.tu-graz.ac.at\/ karisch\/rep287.ps for updates.","journal-title":"European Journal of Operations Research"},{"key":"157589_CR7","unstructured":"R.E. Burkard and E. \u00c7ela, \u201cQuadratic and three-dimensional assignment problems,\u201d Technical report SFB report 63, Institute of Mathematics, University of Technology Graz, 1996."},{"issue":"4","key":"157589_CR8","doi-asserted-by":"crossref","first-page":"696","DOI":"10.1137\/0803036","volume":"3","author":"T.J. Carpenter","year":"1993","unstructured":"T.J. Carpenter, I.J. Lustig, R.E. Marsten, and D.F. Shanno, \u201cHigher-order predictor-corrector interior point methods with application to quadratic objectives,\u201d SIAM Journal on Optimization, vol. 3, no.4, pp. 696-725, 1993.","journal-title":"SIAM Journal on Optimization"},{"key":"157589_CR9","unstructured":"J. Clausen, A. Bruengger, M. Perregard, and A. Marzatta, \u201cJoining forces in problem solving: Combining problem-specific knowledge and high-performance hardware by a parallel search library to solve large-scale quadratic assignment problems,\u201d Technical report, University of Copenhagen, 1996a."},{"key":"157589_CR10","unstructured":"J. Clausen, S.E. Karisch, M. Perregard, and F. Rendl, \u201cOn the applicability of lower bounds for solving rectilinear quadratic assignment problems in parallel,\u201d Technical report, Institute of Mathematics, University of Technology Graz, 1996b."},{"key":"157589_CR11","first-page":"157","volume-title":"Linear Equalities and Related Systems","author":"R.J. Duffin","year":"1956","unstructured":"R.J. Duffin, \u201cInfinite programs,\u201d in Linear Equalities and Related Systems, A.W. Tucker (Ed.), Princeton University Press: Princeton, NJ, 1956, pp. 157-170."},{"key":"157589_CR12","first-page":"61","volume":"31","author":"G. Finke","year":"1987","unstructured":"G. Finke, R.E. Burkard, and F. Rendl, \u201cQuadratic assignment problems,\u201d Annals of Discrete Mathematics, vol. 31, pp. 61-82, 1987.","journal-title":"Annals of Discrete Mathematics"},{"key":"157589_CR13","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0110022","volume":"10","author":"P.C. Gilmore","year":"1962","unstructured":"P.C. Gilmore, \u201cOptimal and suboptimal algorithms for the quadratic assignment problem,\u201d SIAM Journal on Applied Mathematics, vol. 10, pp. 305-313, 1962.","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"157589_CR14","doi-asserted-by":"crossref","unstructured":"M.X. Goemans and D.P. Williamson, \u201c.878-Approximation algorithms for MAX CUT and MAX 2SAT,\u201d in ACM Symposium on Theory of Computing (STOC), 1994.","DOI":"10.1145\/195058.195216"},{"issue":"6","key":"157589_CR15","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"M.X. Goemans and D.P. Williamson, \u201cImproved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming,\u201d Journal of Association for Computing Machinery, vol. 42, no.6, pp. 1115-1145, 1995.","journal-title":"Journal of Association for Computing Machinery"},{"key":"157589_CR16","doi-asserted-by":"crossref","first-page":"727","DOI":"10.1287\/moor.17.3.727","volume":"17","author":"S.W. Hadley","year":"1992","unstructured":"S.W. Hadley, F. Rendl, and H. Wolkowicz, \u201cA new lower bound via projection for the quadratic assignment problem,\u201d Mathematics of Operations Research, vol. 17, pp. 727-739, 1992.","journal-title":"Mathematics of Operations Research"},{"key":"157589_CR17","volume-title":"An interior point method for semidefinite programming and max-cut bounds","author":"C. Helmberg","year":"1994","unstructured":"C. Helmberg, \u201cAn interior point method for semidefinite programming and max-cut bounds,\u201d Ph.D. thesis, Graz University of Technology, Austria, 1994."},{"key":"157589_CR18","first-page":"124","volume":"920","author":"C. Helmberg","year":"1995","unstructured":"C. Helmberg, S. Poljak, F. Rendl, and H. Wolkowicz, \u201cCombining semidefinite and polyhedral relaxations to integer programs,\u201d in Proceedings of the 4th International IPCO Conference, volume 920 of Lecture Notes in Computer Science, Springer, 1995, pp. 124-134.","journal-title":"Proceedings of the 4th International IPCO Conference"},{"key":"157589_CR19","doi-asserted-by":"crossref","unstructured":"C. Helmberg, F. Rendl, R.J. Vanderbei, and H. Wolkowicz, \u201cAn interior point method for semidefinite programming,\u201d SIAM Journal on Optimization, pp. 342-361, 1996. URL: ftp:\/\/orion.uwaterloo.ca\/pub\/ henry\/reports\/sdp.ps.gz.","DOI":"10.1137\/0806020"},{"key":"157589_CR20","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511810817","volume-title":"Matrix Analysis","author":"R. Horn","year":"1985","unstructured":"R. Horn and C. Johnson, Matrix Analysis. Cambridge University Press: New York, 1985."},{"key":"157589_CR21","series-title":"Technical report Technical report","volume-title":"A basic study of the qap-polytope","author":"M. J\u00fcnger","year":"1995","unstructured":"M. J\u00fcnger and V. Kaibel, \u201cA basic study of the qap-polytope,\u201d Technical report Technical report No. 96.215, Institut f\u00fcr Informatik, Universit\u00e4t zu K\u00f6ln, Germany, 1995."},{"key":"157589_CR22","volume-title":"Nonlinear Approaches for Quadratic Assignment and Graph Partition Problems","author":"S.E. Karisch","year":"1995","unstructured":"S.E. Karisch, \u201cNonlinear Approaches for Quadratic Assignment and Graph Partition Problems,\u201d Ph.D. thesis, University of Graz, Graz, Austria, 1995."},{"issue":"2","key":"157589_CR23","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/BF01585995","volume":"71","author":"S.E. Karisch","year":"1995","unstructured":"S.E. Karisch and F. Rendl, \u201cLower bounds for the quadratic assignment problem via triangle decompositions,\u201d Mathematical Programming, vol. 71, no.2, pp. 137-152, 1995.","journal-title":"Mathematical Programming"},{"key":"157589_CR24","series-title":"Technical report","volume-title":"Interior-point methods for the monotone linear complementarity problem in symmetric matrices","author":"M. Kojima","year":"1994","unstructured":"M. Kojima, S. Shindoh, and S. Hara, \u201cInterior-point methods for the monotone linear complementarity problem in symmetric matrices,\u201d Technical report, Dept. of Information Sciences, Tokyo Institute of Technology, Tokyo, Japan, 1994."},{"key":"157589_CR25","unstructured":"S. Kruk and H. Wolkowicz, \u201cSQ2P, sequential quadratic constrained quadratic programming,\u201d to appear in Proceedings of Nonlinear Programming Conference in Beijing in honour of Professor M.J.D. Powell."},{"key":"157589_CR26","doi-asserted-by":"crossref","first-page":"586","DOI":"10.1287\/mnsc.9.4.586","volume":"9","author":"E. Lawler","year":"1963","unstructured":"E. Lawler, \u201cThe quadratic assignment problem,\u201d Management Science, vol. 9, pp. 586-599, 1963.","journal-title":"Management Science"},{"issue":"2","key":"157589_CR27","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L. Lov\u00e1sz","year":"1991","unstructured":"L. Lov\u00e1sz and A. Schrijver, \u201cCones of matrices and set-functions and 0-1 optimization,\u201d SIAM Journal on Optimization, vol. 1, no.2, pp. 166-190, 1991.","journal-title":"SIAM Journal on Optimization"},{"issue":"3","key":"157589_CR28","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1137\/0802022","volume":"2","author":"I.J. Lustig","year":"1992","unstructured":"I.J. Lustig, R.E. Marsten, and D.F. Shanno, \u201cOn implementing Mehrotra's predictor-Corrector interior point method for linear programming,\u201d SIAM Journal on Optimization, vol. 2, no.3, pp. 435-449, 1992.","journal-title":"SIAM Journal on Optimization"},{"key":"157589_CR29","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1287\/opre.16.1.150","volume":"16","author":"C.E. Nugent","year":"1968","unstructured":"C.E. Nugent, T.E. Vollman, and J. Ruml, \u201cAn experimental comparison of techniques for the assignment of facilities to locations,\u201d Operations Research, vol. 16, pp. 150-173, 1968.","journal-title":"Operations Research"},{"key":"157589_CR30","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/dimacs\/016\/01","volume":"16","author":"P. Pardalos","year":"1994","unstructured":"P. Pardalos, F. Rendl, and H. Wolkowicz, \u201cThe quadratic assignment problem: Asurvey and recent developments,\u201d in Proceedings of the DIMACS Workshop on Quadratic Assignment Problems, volume 16 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, 1994, pp. 1-41.","journal-title":"Proceedings of the DIMACS Workshop on Quadratic Assignment Problems"},{"key":"157589_CR31","series-title":"Technical report","volume-title":"Algorithms for cone-optimization problems and semi-definite programming","author":"G. Pataki","year":"1993","unstructured":"G. Pataki, \u201cAlgorithms for cone-optimization problems and semi-definite programming,\u201d Technical report, GSIA Carnegie Mellon University, Pittsburgh, PA, 1993."},{"key":"157589_CR32","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/BF01100205","volume":"7","author":"S. Poljak","year":"1995","unstructured":"S. Poljak, F. Rendl, and H. Wolkowicz, \u201cA recipe for semidefinite relaxation for (0, 1)-quadratic programming,\u201d Journal of Global Optimization, vol. 7, pp. 51-73, 1995.","journal-title":"Journal of Global Optimization"},{"key":"157589_CR33","series-title":"Technical report","volume-title":"A truncated primal-infeasible dual-fesible network interior point method","author":"L. Portugal","year":"1994","unstructured":"L. Portugal, M.G.C. Resende, G. Veiga, and J. Judice, \u201cA truncated primal-infeasible dual-fesible network interior point method,\u201d Technical report, Universidade de Coimbra, Coimbra, Portugal, 1994."},{"key":"157589_CR34","doi-asserted-by":"crossref","unstructured":"K.G. Ramakrishnan, M.G.C. Resende, and P.M. Pardalos, \u201cA branch and bound algorithm for the quadratic assignment problem using a lower bound based on linear programming,\u201d in State of the Art in Global Optimization: Computational Methods and Applications, C. Floudas and P.M. Pardalos (Eds.), Kluwer Academic Publishers, 1995.","DOI":"10.1007\/978-1-4613-3437-8_5"},{"key":"157589_CR35","doi-asserted-by":"crossref","unstructured":"M. Ramana, L. Tuncel, and H. Wolkowicz, \u201cStrong duality for semidefinite programming,\u201d SIAM Journal on Optimization, to appear, 1997. URL: ftp:\/\/orion.uwaterloo.ca\/pub\/henry\/reports\/strongdual.ps.gz.","DOI":"10.1137\/S1052623495288350"},{"key":"157589_CR36","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/BF01585694","volume":"53","author":"F. Rendl","year":"1992","unstructured":"F. Rendl and H. Wolkowicz, \u201cApplications of parametric programming and eigenvalue maximization to the quadratic assignment problem,\u201d Mathematical Programming, vol. 53, pp. 63-78, 1992.","journal-title":"Mathematical Programming"},{"issue":"5","key":"157589_CR37","doi-asserted-by":"crossref","first-page":"781","DOI":"10.1287\/opre.43.5.781","volume":"43","author":"M.G.C. Resende","year":"1995","unstructured":"M.G.C. Resende, K.G. Ramakrishnan, and Z. Drezner, \u201cComputing lower bounds for the quadratic assignment problem with an interior point algorithm for linear programming,\u201d Operations Research, vol. 43, no.5, pp. 781-791, 1995.","journal-title":"Operations Research"},{"key":"157589_CR38","volume-title":"Scheduling, design and assignment problems with quadratic costs","author":"M. Rijal","year":"1995","unstructured":"M. Rijal, \u201cScheduling, design and assignment problems with quadratic costs,\u201d Ph.D. thesis, New York University, New York, USA, 1995."},{"key":"157589_CR39","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1145\/321958.321975","volume":"23","author":"S. Sahni","year":"1976","unstructured":"S. Sahni and T. Gonzales, \u201cP-complete approximation problems,\u201d Journal of ACM, vol. 23, pp. 555-565, 1976.","journal-title":"Journal of ACM"},{"key":"157589_CR40","first-page":"1","volume":"49","author":"H.D. Sherali","year":"1996","unstructured":"H.D. Sherali and W.P. Adams, \u201cComputational advances using the reformulation-linearlization technique (rlt) to solve discrete and continuous nonconvex problems,\u201d Optima, vol. 49, pp. 1-6, 1996.","journal-title":"Optima"},{"issue":"1","key":"157589_CR41","first-page":"205","volume":"69","author":"L. Vandenberghe","year":"1995","unstructured":"L. Vandenberghe and S. Boyd, \u201cPrimal-dual potential reduction method for problems involving matrix inequalities,\u201d Math. Programming, vol. 69, no.1, pp. 205-236, 1995.","journal-title":"Math. Programming"},{"key":"157589_CR42","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1137\/1038003","volume":"38","author":"L. Vandenberghe","year":"1996","unstructured":"L. Vandenberghe and S. Boyd, \u201cSemidefinite programming,\u201d SIAM Review, vol. 38, pp. 49-95, 1996.","journal-title":"SIAM Review"},{"key":"157589_CR43","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/0024-3795(81)90143-9","volume":"40","author":"H. Wolkowicz","year":"1981","unstructured":"H. Wolkowicz, \u201cSome applications of optimization in matrix theory,\u201d Linear Algebra and its Applications vol. 40, pp. 101-118, 1981.","journal-title":"Linear Algebra and its Applications"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1009795911987.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1009795911987\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1009795911987.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T11:13:31Z","timestamp":1751282011000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1009795911987"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,3]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1998,3]]}},"alternative-id":["157589"],"URL":"https:\/\/doi.org\/10.1023\/a:1009795911987","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,3]]}}}