{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:22Z","timestamp":1740122422932,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2-4","license":[{"start":{"date-parts":[[2022,9,29]],"date-time":"2022-09-29T00:00:00Z","timestamp":1664409600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,9,29]],"date-time":"2022-09-29T00:00:00Z","timestamp":1664409600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11601183","61872162"],"award-info":[{"award-number":["11601183","61872162"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2023,11]]},"DOI":"10.1007\/s10898-022-01235-y","type":"journal-article","created":{"date-parts":[[2022,9,29]],"date-time":"2022-09-29T02:04:01Z","timestamp":1664417041000},"page":"857-876","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A note on the SDP relaxation of the minimum cut problem"],"prefix":"10.1007","volume":"87","author":[{"given":"Hao","family":"Hu","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6392-701X","authenticated-orcid":false,"given":"Xinxin","family":"Li","sequence":"additional","affiliation":[]},{"given":"Jiageng","family":"Wu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,9,29]]},"reference":[{"key":"1235_CR1","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."},{"issue":"2","key":"1235_CR2","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/0022-0000(84)90071-0","volume":"28","author":"S Bhatt","year":"1984","unstructured":"Bhatt, S., Leighton, F.: A framework for solving vlsi graph layout problems. J. Comput. Syst. Sci. 28(2), 300\u2013343 (1984)","journal-title":"J. Comput. Syst. Sci."},{"key":"1235_CR3","doi-asserted-by":"crossref","unstructured":"Borwein, J., Wolkowicz, H.: Characterization of optimality for the abstract convex program with finite-dimensional range. J. Austral. Math. Soc. Ser. A 30(4), 390\u2013411 (1980\/81)","DOI":"10.1017\/S1446788700017882"},{"key":"1235_CR4","doi-asserted-by":"crossref","unstructured":"Borwein, J., Wolkowicz, H.: Facial reduction for a cone-convex programming problem. J. Austral. Math. Soc. Ser. A 30(3), 369\u2013380 (1980\/81)","DOI":"10.1017\/S1446788700017250"},{"issue":"2","key":"1235_CR5","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1016\/0022-247X(81)90138-4","volume":"83","author":"J Borwein","year":"1981","unstructured":"Borwein, J., Wolkowicz, H.: Regularizing the abstract convex program. J. Math. Anal. Appl. 83(2), 495\u2013530 (1981)","journal-title":"J. Math. Anal. Appl."},{"key":"1235_CR6","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., Martin, S.: The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut. Discrete Appl. Math. 256, 11\u201337 (2019). https:\/\/doi.org\/10.1016\/j.dam.2018.10.005","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"1235_CR7","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). https:\/\/doi.org\/10.1007\/s10898-010-9568-y","journal-title":"J. Global Optim."},{"key":"1235_CR8","doi-asserted-by":"publisher","unstructured":"Drusvyatskiy, D., Wolkowicz, H.: The many faces of degeneracy in conic optimization. Found. Trends\u00ae Optim. 3(2), 77\u2013170 (2017). https:\/\/doi.org\/10.1561\/2400000011","DOI":"10.1561\/2400000011"},{"key":"1235_CR9","doi-asserted-by":"crossref","unstructured":"Fu, B., Oprisan, S., Xu, L.: Multi-directional width-bounded geometric separator and protein folding. In: International Symposium on Algorithms and Computation, pp. 995\u20131006. Springer (2005)","DOI":"10.1007\/11602613_99"},{"key":"1235_CR10","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/BF02614319","volume":"79","author":"K Fujisawa","year":"1997","unstructured":"Fujisawa, K., Kojima, M., Nakata, K.: Exploiting sparsity in primal-dual interior-point methods for semidefinite programming. Math. Program. 79, 235\u2013253 (1997)","journal-title":"Math. Program."},{"key":"1235_CR11","doi-asserted-by":"publisher","unstructured":"Graham, N., Hu, H., Im, H., Li, X., Wolkowicz, H.: A restricted dual Peaceman-Rachford splitting method for QAP. INFORMS J. Comput. (2022). https:\/\/doi.org\/10.1287\/ijoc.2022.1161","DOI":"10.1287\/ijoc.2022.1161"},{"issue":"1","key":"1235_CR12","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/s10589-017-9945-2","volume":"69","author":"W Hager","year":"2018","unstructured":"Hager, W., Hungerford, J., Safro, I.: A multilevel bilinear programming algorithm for the vertex separator problem. Comput. Optim. Appl. 69(1), 189\u2013223 (2018). https:\/\/doi.org\/10.1007\/s10589-017-9945-2","journal-title":"Comput. Optim. Appl."},{"issue":"3","key":"1235_CR13","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). https:\/\/doi.org\/10.1137\/13090849X","journal-title":"SIAM J. Optim."},{"key":"1235_CR14","doi-asserted-by":"crossref","unstructured":"Hu, H., Sotirov, R., Wolkowicz, H.: Facial reduction for symmetry reduced semidefinite doubly nonnegative programs (2022)","DOI":"10.1007\/s10107-022-01890-9"},{"key":"1235_CR15","unstructured":"Jiang, R., Liu, Y.F., Bao, C., Jiang, B.: Tightness and equivalence of semidefinite relaxations for MIMO detection (2021)"},{"key":"1235_CR16","unstructured":"Leighton, F.: Complexity issues in VLSI: Optimal layouts for the shuffle-exchange graph and other networks (1983)"},{"key":"1235_CR17","unstructured":"Lewis, R.: Yet another graph partitioning problem is NP-hard. Technical report (2014). arXiv:1403.5544"},{"key":"1235_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-020-00261-4","author":"X Li","year":"2021","unstructured":"Li, X., Pong, T.K., Sun, H., Wolkowicz, H.: A strictly contractive Peaceman-Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem. Comput. Optim. Appl. (2021). https:\/\/doi.org\/10.1007\/s10589-020-00261-4","journal-title":"Comput. Optim. Appl."},{"issue":"2","key":"1235_CR19","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1137\/0716027","volume":"16","author":"R Lipton","year":"1979","unstructured":"Lipton, R., Rose, D., Tarjan, R.: Generalized nested dissection. SIAM J. Numer. Anal. 16(2), 346\u2013358 (1979)","journal-title":"SIAM J. Numer. Anal."},{"issue":"3","key":"1235_CR20","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R Lipton","year":"1980","unstructured":"Lipton, R., Tarjan, R.: Applications of a planar separator theorem. SIAM J. Comput. 9(3), 615\u2013627 (1980)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1235_CR21","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":"1","key":"1235_CR22","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1137\/17M115075X","volume":"29","author":"C Lu","year":"2019","unstructured":"Lu, C., Liu, Y.F., Zhang, W.Q., Zhang, S.: Tightness of a new and enhanced semidefinite relaxation for MIMO detection. SIAM J. Optim. 29(1), 719\u2013742 (2019). https:\/\/doi.org\/10.1137\/17M115075X","journal-title":"SIAM J. Optim."},{"issue":"2","key":"1235_CR23","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1137\/S1064827594262613","volume":"19","author":"G Miller","year":"1998","unstructured":"Miller, G., Teng, S.H., Thurston, W., Vavasis, S.: Geometric separators for finite-element meshes. SIAM J. Sci. Comput. 19(2), 364\u2013386 (1998)","journal-title":"SIAM J. Sci. Comput."},{"issue":"2","key":"1235_CR24","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/s10589-015-9779-8","volume":"63","author":"T Pong","year":"2016","unstructured":"Pong, T., 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). https:\/\/doi.org\/10.1007\/s10589-015-9779-8","journal-title":"Comput. Optim. Appl."},{"key":"1235_CR25","doi-asserted-by":"publisher","unstructured":"Pothen, A.: Graph partitioning algorithms with applications to scientific computing. In: Parallel numerical algorithms (Hampton, VA, 1994), ICASE\/LaRC Interdiscip. Ser. Sci. Eng., vol.\u00a04, pp. 323\u2013368. Kluwer Academic Publishers, Dordrecht (1997). https:\/\/doi.org\/10.1007\/978-94-011-5412-3_12","DOI":"10.1007\/978-94-011-5412-3_12"},{"issue":"1","key":"1235_CR26","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1137\/050637467","volume":"18","author":"J Povh","year":"2007","unstructured":"Povh, J., Rendl, F.: A copositive programming approach to graph partitioning. SIAM J. Optim. 18(1), 223\u2013241 (2007)","journal-title":"SIAM J. Optim."},{"key":"1235_CR27","doi-asserted-by":"crossref","unstructured":"Rendl, F., Lisser, A., Piacentini, M.: Bandwidth, vertex separators and eigenvalue optimization. In: Discrete Geometry and Optimization. In: The Fields Institute for Research in Mathematical Sciences, Communications Series, vol.\u00a069, pp. 249\u2013263. Springer (2013)","DOI":"10.1007\/978-3-319-00200-2_14"},{"issue":"1","key":"1235_CR28","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":"1235_CR29","first-page":"1","volume":"49","author":"H Sherali","year":"1996","unstructured":"Sherali, H., Adams, W.: Computational advances using the reformulation-linearization technique (RLT) to solve discrete and continuous nonconvex problems. Optima 49, 1\u20136 (1996)","journal-title":"Optima"},{"issue":"97","key":"1235_CR30","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)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"1235_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., Rendl, F., Wolkowicz, H.: Semidefinite programming relaxations for the quadratic assignment problem. J. Comb. Optim. 2(1), 71\u2013109 (1998). https:\/\/doi.org\/10.1023\/A:1009795911987","journal-title":"J. Comb. Optim."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-022-01235-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-022-01235-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-022-01235-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,31]],"date-time":"2023-10-31T19:57:24Z","timestamp":1698782244000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-022-01235-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,29]]},"references-count":31,"journal-issue":{"issue":"2-4","published-print":{"date-parts":[[2023,11]]}},"alternative-id":["1235"],"URL":"https:\/\/doi.org\/10.1007\/s10898-022-01235-y","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"type":"print","value":"0925-5001"},{"type":"electronic","value":"1573-2916"}],"subject":[],"published":{"date-parts":[[2022,9,29]]},"assertion":[{"value":"30 August 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 August 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 September 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}