{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,22]],"date-time":"2026-02-22T08:22:29Z","timestamp":1771748549764,"version":"3.50.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,1,22]],"date-time":"2021-01-22T00:00:00Z","timestamp":1611273600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,22]],"date-time":"2021-01-22T00:00:00Z","timestamp":1611273600000},"content-version":"vor","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":[[2021,4]]},"DOI":"10.1007\/s10589-020-00261-4","type":"journal-article","created":{"date-parts":[[2021,1,22]],"date-time":"2021-01-22T17:27:47Z","timestamp":1611336467000},"page":"853-891","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["A strictly contractive Peaceman-Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem"],"prefix":"10.1007","volume":"78","author":[{"given":"Xinxin","family":"Li","sequence":"first","affiliation":[]},{"given":"Ting Kei","family":"Pong","sequence":"additional","affiliation":[]},{"given":"Hao","family":"Sun","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1572-3060","authenticated-orcid":false,"given":"Henry","family":"Wolkowicz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,1,22]]},"reference":[{"key":"261_CR1","unstructured":"MOSEK ApS. The MOSEK optimization toolbox for MATLAB manual. Version 8.1., (2017). http:\/\/docs.mosek.com\/8.0\/toolbox\/index.html"},{"key":"261_CR2","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. Programm. 58, 295\u2013324 (1993)","journal-title":"Math. Programm."},{"issue":"1","key":"261_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/2200000016","volume":"3","author":"S Boyd","year":"2011","unstructured":"Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3(1), 1\u2013122 (2011)","journal-title":"Found. Trends Mach. Learn."},{"key":"261_CR4","doi-asserted-by":"crossref","unstructured":"B\u00fccker, H.M., Rostami, M.A.: Interactively exploring the connection between nested dissection orderings for parallel cholesky factorization and vertex separators. In: 2014 IEEE International Parallel Distributed Processing Symposium Workshops, pp. 1122\u20131129 (2014)","DOI":"10.1109\/IPDPSW.2014.125"},{"issue":"4","key":"261_CR5","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1287\/ijoc.1040.0096","volume":"16","author":"Bernard Chazelle","year":"2004","unstructured":"Chazelle, Bernard: Kingsford, Carl, Singh, Mona: a semidefinite programming approach to side chain positioning with new rounding strategies. INFORMS J. Comput. 16(4), 380\u2013392 (2004)","journal-title":"INFORMS J. Comput."},{"key":"261_CR6","unstructured":"Chen, Y., Ye, X.: Projection onto a simplex. arXiv preprint. arXiv:1101.6081, (2011)"},{"key":"261_CR7","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.dam.2018.10.005","volume":"256","author":"D Cornaz","year":"2019","unstructured":"Cornaz, D., Magnouche, Y., Mahjoub, A.R., Martin, S.: The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut. Dis. Appl. Math. 256, 11\u201337 (2019)","journal-title":"Dis. Appl. Math."},{"issue":"3","key":"261_CR8","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1007\/s10898-010-9568-y","volume":"49","author":"M Didi Biha","year":"2011","unstructured":"Didi Biha, M., Meurs, M.-J.: An exact algorithm for solving the vertex separator problem. J. Global Optim. 49(3), 425\u2013434 (2011)","journal-title":"J. Global Optim."},{"key":"261_CR9","volume-title":"Graph theory and sparse matrix computation","author":"Alan George","year":"2012","unstructured":"George, Alan, Gilbert, John R., Liu, Joseph W.H.: Graph theory and sparse matrix computation, vol. 56. Springer, Berlin (2012)"},{"issue":"1","key":"261_CR10","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/s10589-017-9945-2","volume":"69","author":"WW Hager","year":"2018","unstructured":"Hager, W.W., Hungerford, J.T., Safro, I.: A multilevel bilinear programming algorithm for the vertex separator problem. Comput. Optim. Appl. 69(1), 189\u2013223 (2018)","journal-title":"Comput. Optim. Appl."},{"issue":"3","key":"261_CR11","doi-asserted-by":"publisher","first-page":"1011","DOI":"10.1137\/13090849X","volume":"24","author":"B He","year":"2014","unstructured":"He, B., Liu, H., Wang, Z., Yuan, X.: A strictly contractive Peaceman-Rachford splitting method for convex programming. SIAM J. Optim. 24(3), 1011\u20131040 (2014)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"261_CR12","doi-asserted-by":"publisher","first-page":"1467","DOI":"10.1137\/15M1044448","volume":"9","author":"Bingsheng He","year":"2016","unstructured":"He, Bingsheng: Ma, Feng, Yuan, Xiaoming: convergence study on the symmetric version of ADMM with larger step sizes. SIAM J. Imag. Sci. 9(3), 1467\u20131501 (2016)","journal-title":"SIAM J. Imag. Sci."},{"issue":"7","key":"261_CR13","doi-asserted-by":"publisher","first-page":"1028","DOI":"10.1093\/bioinformatics\/bti144","volume":"21","author":"Carleton L Kingsford","year":"2005","unstructured":"Kingsford, Carleton L.: Chazelle, Bernard, Singh, Mona: Solving and analyzing side-chain positioning problems using linear and integer programming. Bioinformatics 21(7), 1028\u20131039 (2005)","journal-title":"Bioinformatics"},{"issue":"4","key":"261_CR14","first-page":"21","volume":"8","author":"Carlos Lara","year":"2009","unstructured":"Lara, Carlos, Flores, Juan J., Calderon, Felix: On the hyperbox-hyperplane intersection problem. INFOCOMP J. Comp. Sci. 8(4), 21\u201327 (2009)","journal-title":"INFOCOMP J. Comp. Sci."},{"key":"261_CR15","unstructured":"Lewis, R.H.: Yet another graph partitioning problem is NP-hard. Technical report, (2014)"},{"issue":"2","key":"261_CR16","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":"3","key":"261_CR17","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1023\/A:1023997605430","volume":"117","author":"N Maculan","year":"2003","unstructured":"Maculan, N., Santiago, C.P., Macambira, E.M., Jardim, M.H.C.: An $$O(n)$$ algorithm for projecting a vector on the intersection of a hyperplane and a box in $${\\mathbb{R}}^n$$. J. Optim. Theory Appl. 117(3), 553\u2013574 (2003)","journal-title":"J. Optim. Theory Appl."},{"issue":"4","key":"261_CR18","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1007\/s12532-018-0148-3","volume":"10","author":"DE Oliveira","year":"2018","unstructured":"Oliveira, D.E., Wolkowicz, H., Xu, Y.: ADMM for the SDP relaxation of the QAP. Math. Program. Comput. 10(4), 631\u2013658 (2018)","journal-title":"Math. Program. Comput."},{"issue":"2","key":"261_CR19","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/s10589-015-9779-8","volume":"63","author":"TK Pong","year":"2016","unstructured":"Pong, T.K., Sun, H., Wang, N., Wolkowicz, H.: Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem. Comput. Optim. Appl. 63(2), 333\u2013364 (2016)","journal-title":"Comput. Optim. Appl."},{"key":"261_CR20","doi-asserted-by":"crossref","unstructured":"Pothen, A.: Graph partitioning algorithms with applications to scientific computing. In: Keyes, D.E., Sameh, A., Venkatakrishnan, V. (eds.) Parallel Numerical Algorithms.  ICASE\/LaRC Interdisciplinary Series in Science and Engineering, vol. 4, pp. 323\u2013368.  Kluwer Academic Press, Dordrecht (1997)","DOI":"10.1007\/978-94-011-5412-3_12"},{"key":"261_CR21","doi-asserted-by":"crossref","unstructured":"Rendl, F., Lisser, A., Piacentini, M.: Bandwidth, vertex separators and eigenvalue optimization. In: Bezdek, K., Deza, A., Ye, Y. (eds.) Discrete Geometry and Optimization. Fields Institute Communications, vol. 69, pp. 29\u2013263. Springer (2013)","DOI":"10.1007\/978-3-319-00200-2_14"},{"issue":"1","key":"261_CR22","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/s10589-017-9943-4","volume":"69","author":"F Rendl","year":"2018","unstructured":"Rendl, F., Sotirov, R.: The min-cut and vertex separator problem. Comput. Optim. Appl. 69(1), 159\u2013187 (2018)","journal-title":"Comput. Optim. Appl."},{"key":"261_CR23","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1287\/moor.1.2.130","volume":"1","author":"SM Robinson","year":"1976","unstructured":"Robinson, S.M.: Regularity and stability for convex multivalued functions. Math. Oper. Res. 1, 130\u2013143 (1976)","journal-title":"Math. Oper. Res."},{"key":"261_CR24","unstructured":"Rockafellar, R.T.: Convex analysis. Princeton Landmarks in Mathematics. Princeton University Press, Princeton, NJ, 1997. Reprint of the 1970 original, Princeton Paperbacks"},{"key":"261_CR25","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"},{"key":"261_CR26","unstructured":"Simpson, Toby: Sparse cholesky reordering with the graph $$p$$-laplacian. Master\u2019s thesis, Universit\u00e1 della Svizzera Italiana, (2017)"},{"key":"261_CR27","unstructured":"Sun, H.: ADMM for SDP relaxation of GP. Master\u2019s thesis, University of Waterloo, (2016)"},{"issue":"2","key":"261_CR28","doi-asserted-by":"publisher","first-page":"890","DOI":"10.1137\/080714488","volume":"31","author":"E van den Berg","year":"2008","unstructured":"van den Berg, E., Friedlander, M.P.: Probing the Pareto frontier for basis pursuit solutions. SIAM J. Sci. Comput. 31(2), 890\u2013912 (2008)","journal-title":"SIAM J. Sci. Comput."},{"key":"261_CR29","doi-asserted-by":"crossref","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)","DOI":"10.1016\/S0166-218X(99)00102-X"},{"key":"261_CR30","unstructured":"Zhao, Q.: Semidefinite Programming for Assignment and Partitioning Problems. PhD thesis, University of Waterloo, (1996)"},{"key":"261_CR31","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, 71\u2013109 (1998)","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-020-00261-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10589-020-00261-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-020-00261-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,25]],"date-time":"2021-02-25T17:32:06Z","timestamp":1614274326000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10589-020-00261-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,22]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["261"],"URL":"https:\/\/doi.org\/10.1007\/s10589-020-00261-4","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,22]]},"assertion":[{"value":"22 October 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 December 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 January 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}