{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T08:47:52Z","timestamp":1774946872391,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,8,21]],"date-time":"2015-08-21T00:00:00Z","timestamp":1440115200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2015,8,21]],"date-time":"2015-08-21T00:00:00Z","timestamp":1440115200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100009059","name":"Pacific Institute for the Mathematical Sciences","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100009059","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000038","name":"Natural Science and Engineering Research Council of Canada","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2016,3]]},"DOI":"10.1007\/s10589-015-9779-8","type":"journal-article","created":{"date-parts":[[2015,8,20]],"date-time":"2015-08-20T13:18:51Z","timestamp":1440076731000},"page":"333-364","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem"],"prefix":"10.1007","volume":"63","author":[{"given":"Ting Kei","family":"Pong","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hao","family":"Sun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ningchuan","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Henry","family":"Wolkowicz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,8,21]]},"reference":[{"issue":"3, Ser. A","key":"9779_CR1","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/PL00011402","volume":"89","author":"KM Anstreicher","year":"2001","unstructured":"Anstreicher, K.M., Brixius, N.W.: A new bound for the quadratic assignment problem based on convex quadratic programming. Math. Program. 89(3, Ser. A), 341\u2013357 (2001)","journal-title":"Math. Program."},{"issue":"1","key":"9779_CR2","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1137\/S0895479898340299","volume":"22","author":"KM Anstreicher","year":"2000","unstructured":"Anstreicher, K.M., Wolkowicz, H.: On Lagrangian relaxation of quadratic matrix constraints. SIAM J. Matrix Anal. Appl. 22(1), 41\u201355 (2000)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"9779_CR3","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01581273","volume":"58","author":"E Balas","year":"1993","unstructured":"Balas, E., Ceria, S., Cornuejols, G.: A lift-and-project cutting plane algorithm for mixed 0\u20131 programs. Math. Program. 58, 295\u2013324 (1993)","journal-title":"Math. Program."},{"key":"9779_CR4","doi-asserted-by":"crossref","unstructured":"Borwein, J.M., Wolkowicz, H.: Facial reduction for a cone-convex programming problem. J. Aust. Math. Soc. A 30(3), 369\u2013380 (1980\/1981)","DOI":"10.1017\/S1446788700017250"},{"issue":"1\u20134","key":"9779_CR5","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1080\/10556780108805828","volume":"16","author":"NW Brixius","year":"2001","unstructured":"Brixius, N.W., Anstreicher, K.M.: Solving quadratic assignment problems using convex quadratic programming relaxations. Optim. Methods Softw. 16(1\u20134), 49\u201368 (2001). Dedicated to Professor Laurence C. W. Dixon on the occasion of his 65th birthday","journal-title":"Optim. Methods Softw."},{"key":"9779_CR6","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107325708","volume-title":"Combinatorial Matrix Theory","author":"RA Brualdi","year":"1991","unstructured":"Brualdi, R.A., Ryser, H.J.: Combinatorial Matrix Theory. Cambridge University Press, New York (1991)"},{"key":"9779_CR7","first-page":"225","volume-title":"Computational andAnalytical Mathematics. In Honor of Jonathan Borwein\u2019s 60thBirthday. Springer Proceedings in Mathematics & Statistics","author":"Y-L Cheung","year":"2013","unstructured":"Cheung, Y.-L., Schurr, S., Wolkowicz, H.: Preprocessing and regularization for degenerate semidefinite programs. In: Bailey, D.H., Bauschke, H.H., Borwein, P., Garvan, F., Thera, M., Vanderwerff, J., Wolkowicz, H. (eds.) Computational andAnalytical Mathematics. In Honor of Jonathan Borwein\u2019s 60thBirthday. Springer Proceedings in Mathematics & Statistics, vol. 50, pp. 225\u2013276. Springer, New York (2013)"},{"issue":"3","key":"9779_CR8","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1080\/10556788.2012.709856","volume":"28","author":"E de Klerk","year":"2013","unstructured":"de Klerk, E., Nagy, M.E., Sotirov, R.: On semidefinite programming bounds for graph bandwidth. Optim. Methods Softw. 28(3), 485\u2013500 (2013)","journal-title":"Optim. Methods Softw."},{"key":"9779_CR9","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971446","volume-title":"Applied Numerical Linear Algebra","author":"JW Demmel","year":"1997","unstructured":"Demmel, J.W.: Applied Numerical Linear Algebra. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (1997)"},{"issue":"2, Ser. A","key":"9779_CR10","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/BF01581147","volume":"66","author":"J Falkner","year":"1994","unstructured":"Falkner, J., Rendl, F., Wolkowicz, H.: A computational study of graph partitioning. Math. Program. 66(2, Ser. A), 211\u2013239 (1994)","journal-title":"Math. Program."},{"key":"9779_CR11","doi-asserted-by":"crossref","unstructured":"Grant, M., Boyd, S., Ye, Y.: Disciplined convex programming. In: Global Optimization. Nonconvex Global Optimization, vol. 84, pp. 155\u2013210. Springer, New York (2006)","DOI":"10.1007\/0-387-30528-9_7"},{"issue":"3","key":"9779_CR12","doi-asserted-by":"publisher","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(3), 727\u2013739 (1992)","journal-title":"Math. Oper. Res."},{"key":"9779_CR13","unstructured":"Hager, W.W., Hungerford, J.T.: A continuous quadratic programming formulation of the vertex separator problem. Report, University of Florida, Gainesville (2013)"},{"key":"9779_CR14","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1215\/S0012-7094-53-02004-3","volume":"20","author":"AJ Hoffman","year":"1953","unstructured":"Hoffman, A.J., Wielandt, H.W.: The variation of the spectrum of a normal matrix. Duke Math. 20, 37\u201339 (1953)","journal-title":"Duke Math."},{"key":"9779_CR15","unstructured":"Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1990). Corrected reprint of the 1985 original"},{"key":"9779_CR16","unstructured":"Lewis, R.H.: Yet another graph partitioning problem is NP-Hard. Report. \n                    arXiv:1403.5544\n                    \n                   [cs.CC] (2014)"},{"issue":"2","key":"9779_CR17","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz, L., Schrijver, A.: Cones of matrices and set-functions and 0\u20131 optimization. SIAM J. Optim. 1(2), 166\u2013190 (1991)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"9779_CR18","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1016\/j.ejor.2007.02.004","volume":"186","author":"R Mart\u00ed","year":"2008","unstructured":"Mart\u00ed, R., Campos, V., Pi\u00f1ana, E.: A branch and bound algorithm for the matrix bandwidth minimization. Eur. J. Oper. Res. 186(2), 513\u2013528 (2008)","journal-title":"Eur. J. Oper. Res."},{"key":"9779_CR19","unstructured":"Povh, J., Rendl, F.: Approximating non-convex quadratic programs by semidefinite and copositive programming. In: KOI 2006\u201411th International Conference on Operational Research, pp. 35\u201345. Croatian Operational Research Review, Zagreb (2008)"},{"issue":"1, Ser. A","key":"9779_CR20","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/BF01585694","volume":"53","author":"F Rendl","year":"1992","unstructured":"Rendl, F., Wolkowicz, H.: Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem. Math. Program. 53(1, Ser. A), 63\u201378 (1992)","journal-title":"Math. Program."},{"key":"9779_CR21","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/BF02032130","volume":"58","author":"F Rendl","year":"1995","unstructured":"Rendl, F., Wolkowicz, H.: A projection technique for partitioning the nodes of a graph. Ann. Oper. Res. 58, 155\u2013179 (1995). Applied mathematical programming and modeling, II (APMOD 93) (Budapest, 1993)","journal-title":"Ann. Oper. Res."},{"key":"9779_CR22","doi-asserted-by":"crossref","unstructured":"Rendl, F., Lisser, A., Piacentini, M.: Bandwidth, vertex separators and eigenvalue optimization. In: Discrete Geometry and Optimization. The Fields Institute for Research in Mathematical Sciences. Communications Series. pp. 249\u2013263. Springer, New York (2013)","DOI":"10.1007\/978-3-319-00200-2_14"},{"key":"9779_CR23","volume-title":"Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics","author":"A Schrijver","year":"1986","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics. Wiley, Chichester (1986)"},{"key":"9779_CR24","first-page":"1","volume":"49","author":"HD Sherali","year":"1996","unstructured":"Sherali, H.D., Adams, W.P.: Computational advances using the reformulation-linearization technique (rlt) to solve discrete and continuous nonconvex problems. Optima 49, 1\u20136 (1996)","journal-title":"Optima"},{"issue":"2","key":"9779_CR25","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1287\/opre.34.2.250","volume":"34","author":"E Tardos","year":"1986","unstructured":"Tardos, E.: A strongly polynomial algorithm to solve combinatorial linear programs. Oper. Res. 34(2), 250\u2013256 (1986)","journal-title":"Oper. Res."},{"key":"9779_CR26","unstructured":"Tardos, E.: Strongly polynomial and combinatorial algorithms in optimization. In: Proceedings of the International Congress of Mathematicians, Vol. I, II (Kyoto, 1990), pp. 1467\u20131478. Mathematical Society of Japan, Tokyo (1991)"},{"issue":"2, Ser. B","key":"9779_CR27","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/s10107-002-0347-5","volume":"95","author":"RH T\u00fct\u00fcnc\u00fc","year":"2003","unstructured":"T\u00fct\u00fcnc\u00fc, R.H., Toh, K.C., Todd, M.J.: Solving semidefinite-quadratic-linear programs using SDPT3. Math. Program. 95(2, Ser. B), 189\u2013217 (2003). Computational semidefinite and second order cone programming: the state of the art","journal-title":"Math. Program."},{"issue":"97","key":"9779_CR28","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1016\/S0166-218X(99)00102-X","volume":"96","author":"H Wolkowicz","year":"1999","unstructured":"Wolkowicz, H., Zhao, Q.: Semidefinite programming relaxations for the graph partitioning problem. Discrete Appl. Math. 96(97), 461\u2013479 (1999). Selected for the special Editors\u2019 Choice, Edition 1999","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"9779_CR29","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1023\/A:1009795911987","volume":"2","author":"Q Zhao","year":"1998","unstructured":"Zhao, Q., Karisch, S.E., Rendl, F., Wolkowicz, H.: Semidefinite programming relaxations for the quadratic assignment problem. J. Comb. Optim. 2(1), 71\u2013109 (1998). Semidefinite programming and interior-point approaches for combinatorial optimization problems (Fields Institute, Toronto, ON, 1996)","journal-title":"J. Comb. Optim."}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-015-9779-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10589-015-9779-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-015-9779-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-015-9779-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T10:52:34Z","timestamp":1589712754000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10589-015-9779-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,8,21]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,3]]}},"alternative-id":["9779"],"URL":"https:\/\/doi.org\/10.1007\/s10589-015-9779-8","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,8,21]]},"assertion":[{"value":"20 January 2014","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 August 2015","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}