{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,23]],"date-time":"2025-07-23T12:36:50Z","timestamp":1753274210725,"version":"3.37.3"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,3,20]],"date-time":"2023-03-20T00:00:00Z","timestamp":1679270400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,3,20]],"date-time":"2023-03-20T00:00:00Z","timestamp":1679270400000},"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":["12171151","11771243"],"award-info":[{"award-number":["12171151","11771243"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007703","name":"North Carolina State University","doi-asserted-by":"publisher","award":["Walter Clark Endowment"],"award-info":[{"award-number":["Walter Clark Endowment"]}],"id":[{"id":"10.13039\/100007703","id-type":"DOI","asserted-by":"publisher"}]},{"name":"MOE Social Science Laboratory of Digital Economic Forecast and Policy Simulation at UCAS","award":["N.A.","T2293774"],"award-info":[{"award-number":["N.A.","T2293774"]}]},{"DOI":"10.13039\/501100012226","name":"Fundamental Research Funds for the Central Universities","doi-asserted-by":"publisher","award":["E2ET0808X2"],"award-info":[{"award-number":["E2ET0808X2"]}],"id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Optim Theory Appl"],"published-print":{"date-parts":[[2023,5]]},"DOI":"10.1007\/s10957-023-02195-3","type":"journal-article","created":{"date-parts":[[2023,3,27]],"date-time":"2023-03-27T02:10:47Z","timestamp":1679883047000},"page":"608-638","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A New Global Algorithm for Max-Cut Problem with Chordal Sparsity"],"prefix":"10.1007","volume":"197","author":[{"given":"Cheng","family":"Lu","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0563-5841","authenticated-orcid":false,"given":"Zhibin","family":"Deng","sequence":"additional","affiliation":[]},{"given":"Shu-Cherng","family":"Fang","sequence":"additional","affiliation":[]},{"given":"Wenxun","family":"Xing","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,3,20]]},"reference":[{"key":"2195_CR1","doi-asserted-by":"crossref","unstructured":"Andersen, M., Vandenberghe, L., Dahl, J.: Linear matrix inequalities with chordal sparsity patterns and applications to robust quadratic optimization. In: 2010 IEEE International Symposium on Computer-Aided Control System Design (CACSD), pp. 7\u201312 (2010)","DOI":"10.1109\/CACSD.2010.5612788"},{"issue":"2","key":"2195_CR2","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D., Proskurowski, A.: Complexity of finding embeddings in a $$k$$-tree. SIAM. J. Alg. Disc. Meth. 8(2), 277\u2013284 (1987)","journal-title":"SIAM. J. Alg. Disc. Meth."},{"issue":"2","key":"2195_CR3","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1287\/moor.10.2.340","volume":"10","author":"F Barahona","year":"1985","unstructured":"Barahona, F., Gr\u00f6tschel, M., Mahjoub, A.R.: Facets of the bipartite subgraph polytope. Math. Oper. Res. 10(2), 340\u2013358 (1985)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"2195_CR4","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF02592023","volume":"36","author":"F Barahona","year":"1986","unstructured":"Barahona, F., Mahjoub, A.R.: On the cut polytope. Math. Program. Ser. A 36(2), 157\u2013173 (1986)","journal-title":"Math. Program. Ser. A"},{"issue":"3","key":"2195_CR5","doi-asserted-by":"publisher","first-page":"817","DOI":"10.1016\/j.ejor.2021.05.043","volume":"297","author":"S Benati","year":"2021","unstructured":"Benati, S., Ponce, D., Puerto, J., Rodriguez-Chia, A.: A branch-and-price procedure for clustering data that are graph connected. Euro. J. Oper. Res. 297(3), 817\u2013830 (2021)","journal-title":"Euro. J. Oper. Res."},{"issue":"1","key":"2195_CR6","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/s10107-005-0637-9","volume":"109","author":"A Billionnet","year":"2007","unstructured":"Billionnet, A., Elloumi, S.: Using a mixed integer quadratic programming solver for the unconstrained quadratic 0\u20131 problem. Math. Program. Ser. A 109(1), 55\u201368 (2007)","journal-title":"Math. Program. Ser. A"},{"issue":"2","key":"2195_CR7","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1137\/S1052623400382467","volume":"12","author":"S Burer","year":"2002","unstructured":"Burer, S., Monteiro, R.D.C., Zhang, Y.: Rank-two relaxation heuristics for max-cut and other binary quadratic programs. SIAM J. Optim. 12(2), 503\u2013521 (2002)","journal-title":"SIAM J. Optim."},{"key":"2195_CR8","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory, 5th edn. Springer (2017)","DOI":"10.1007\/978-3-662-53622-3"},{"issue":"3","key":"2195_CR9","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1287\/ijoc.2017.0798","volume":"30","author":"I Dunning","year":"2018","unstructured":"Dunning, I., Gupta, S., Silberholz, J.: What works best when? A systematic evaluation of heuristics for max-cut and QUBO. INFORMS J. Comput. 30(3), 608\u2013624 (2018)","journal-title":"INFORMS J. Comput."},{"issue":"3","key":"2195_CR10","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1007\/s10589-017-9967-9","volume":"69","author":"J Fairbrother","year":"2018","unstructured":"Fairbrother, J., Letchford, A.N., Briggs, K.: A two-level graph partitioning problem arising in mobile wireless communications. Comput. Optim. Appl. 69(3), 653\u2013676 (2018)","journal-title":"Comput. Optim. Appl."},{"issue":"6","key":"2195_CR11","doi-asserted-by":"publisher","first-page":"1033","DOI":"10.1080\/1055678021000090033","volume":"17","author":"P Festa","year":"2002","unstructured":"Festa, P., Pardalos, P., Resende, M., Ribeiro, C.: Randomized heuristics for the max-cut problem. Optim. Methods Softw. 17(6), 1033\u20131058 (2002)","journal-title":"Optim. Methods Softw."},{"issue":"3","key":"2195_CR12","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1137\/S1052623400366218","volume":"11","author":"M Fukuda","year":"2001","unstructured":"Fukuda, M., Kojima, M., Murota, K., Nakata, K.: Exploiting sparsity in semidefinite programming via matrix completion I: General framework. SIAM J. Optim. 11(3), 647\u2013674 (2001)","journal-title":"SIAM J. Optim."},{"issue":"1\u20132","key":"2195_CR13","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/s10107-020-01512-2","volume":"183","author":"E Gaar","year":"2020","unstructured":"Gaar, E., Rendl, F.: A computational study of exact subgraph based SDP bounds for Max-Cut, stable set and coloring. Math. Program. Ser. B 183(1\u20132), 283\u2013308 (2020)","journal-title":"Math. Program. Ser. B"},{"key":"2195_CR14","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)"},{"issue":"3","key":"2195_CR15","doi-asserted-by":"publisher","first-page":"779","DOI":"10.1007\/s10957-021-01896-x","volume":"190","author":"M Garstka","year":"2021","unstructured":"Garstka, M., Cannon, M., Goulart, P.: Cosmo: a conic operator splitting method for convex conic problems. J. Optim. Theory App. 190(3), 779\u2013810 (2021)","journal-title":"J. Optim. Theory App."},{"issue":"6","key":"2195_CR16","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6), 1115\u20131145 (1995)","journal-title":"J. ACM"},{"key":"2195_CR17","doi-asserted-by":"publisher","DOI":"10.1201\/9781315275857","volume-title":"Finite Element Method: Applications in Solids, Structures, and Heat Transfer","author":"M Gosz","year":"2017","unstructured":"Gosz, M.: Finite Element Method: Applications in Solids, Structures, and Heat Transfer. CRC Press, Boca Raton (2017)"},{"key":"2195_CR18","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0024-3795(84)90207-6","volume":"58","author":"R Grone","year":"1984","unstructured":"Grone, R., Johnson, C.R., S\u00e1, E.M., Wolkowicz, H.: Positive definite completions of partial Hermitian matrices. Linear Algebra Appl. 58, 109\u2013124 (1984)","journal-title":"Linear Algebra Appl."},{"issue":"3","key":"2195_CR19","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/j.disc.2005.12.003","volume":"306","author":"P Heggernes","year":"2006","unstructured":"Heggernes, P.: Minimal triangulation of graphs: a survey. Discrete Math. 306(3), 297\u2013317 (2006)","journal-title":"Discrete Math."},{"issue":"3","key":"2195_CR20","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/BF01580072","volume":"82","author":"C Helmberg","year":"1998","unstructured":"Helmberg, C., Rendl, F.: Solving quadratic (0,1)-problems by semidefinite programs and cutting planes. Math. Program. Ser. A 82(3), 291\u2013315 (1998)","journal-title":"Math. Program. Ser. A"},{"issue":"4","key":"2195_CR21","doi-asserted-by":"publisher","first-page":"913","DOI":"10.1007\/s10898-019-00813-x","volume":"76","author":"F Jarre","year":"2020","unstructured":"Jarre, F., Lieder, F., Liu, Y., Lu, C.: Set-completely-positive representations and cuts for the max-cut polytope and the unit modulus lifting. J. Glob. Optim. 76(4), 913\u2013932 (2020)","journal-title":"J. Glob. Optim."},{"issue":"4","key":"2195_CR22","first-page":"1419","volume":"33","author":"M J\u00fcnger","year":"2021","unstructured":"J\u00fcnger, M., Mallach, S.: Exact facetial odd-cycle separation for maximum cut and binary quadratic optimization. INFORMS J. Comput. 33(4), 1419\u20131430 (2021)","journal-title":"INFORMS J. Comput."},{"issue":"3\u20134","key":"2195_CR23","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1080\/10556780108805819","volume":"15","author":"S Kim","year":"2001","unstructured":"Kim, S., Kojima, M.: Second order cone programming relaxation of nonconvex quadratic optimization problems. Optim. Methods Softw. 15(3\u20134), 201\u2013224 (2001)","journal-title":"Optim. Methods Softw."},{"key":"2195_CR24","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/S1571-0653(05)80078-2","volume":"8","author":"AC Koster","year":"2001","unstructured":"Koster, A.C., Bodlaender, H.L., van Hoesel, S.P.: Treewidth: computational experiments. Electron. Notes Discrete Math. 8, 54\u201357 (2001)","journal-title":"Electron. Notes Discrete Math."},{"issue":"1","key":"2195_CR25","first-page":"62","volume":"143","author":"N Krislock","year":"2014","unstructured":"Krislock, N., Malick, J., Roupin, F.: Improved semidefinite bounding procedure for solving max-cut problems to optimality. Math. Program. Ser. A 143(1), 62\u201386 (2014)","journal-title":"Math. Program. Ser. A"},{"issue":"4","key":"2195_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3005345","volume":"43","author":"N Krislock","year":"2017","unstructured":"Krislock, N., Malick, J., Roupin, F.: Biqcrunch: a semidefinite branch-and-bound method for solving binary quadratic problems. ACM T. Math. Softw. 43(4), 1\u201323 (2017)","journal-title":"ACM T. Math. Softw."},{"issue":"2","key":"2195_CR27","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1016\/j.orl.2015.12.014","volume":"44","author":"JB Lasserre","year":"2016","unstructured":"Lasserre, J.B.: A MAX-CUT formulation of 0\/1 programs. Oper. Res. Lett. 44(2), 158\u2013164 (2016)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"2195_CR28","doi-asserted-by":"publisher","first-page":"725","DOI":"10.1137\/14099379X","volume":"27","author":"R Madani","year":"2017","unstructured":"Madani, R., Sojoudi, S., Fazelnia, G., Lavaei, J.: Finding low-rank solutions of sparse linear matrix inequalities using convex optimization. SIAM J. Optim. 27(2), 725\u2013758 (2017)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"2195_CR29","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1287\/ijoc.1080.0275","volume":"21","author":"R Mart\u00ed","year":"2009","unstructured":"Mart\u00ed, R., Duarte, A., Laguna, M.: Advanced scatter search for the max-cut problem. INFORMS J. Comput. 21(1), 26\u201338 (2009)","journal-title":"INFORMS J. Comput."},{"key":"2195_CR30","unstructured":"Mosek: Mosek aps. http:\/\/www.mosek.com (2020)"},{"issue":"2","key":"2195_CR31","first-page":"164","volume":"46","author":"M Muramatsu","year":"2003","unstructured":"Muramatsu, M., Suzuki, T.: A new second-order cone programming relaxation for max-cut problems. J. Oper. Res. Soc. Jpn. 46(2), 164\u2013177 (2003)","journal-title":"J. Oper. Res. Soc. Jpn."},{"issue":"1\u20133","key":"2195_CR32","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0166-218X(94)00155-7","volume":"62","author":"S Poljak","year":"1995","unstructured":"Poljak, S., Rendl, F.: Solving the max-cut problem using eigenvalues. Discrete Appl. Math. 62(1\u20133), 249\u2013278 (1995)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"2195_CR33","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/s10107-008-0235-8","volume":"121","author":"F Rendl","year":"2010","unstructured":"Rendl, F., Rinaldi, G., Wiegele, A.: Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations. Math. Program. Ser. A 121(2), 307\u2013335 (2010)","journal-title":"Math. Program. Ser. A"},{"key":"2195_CR34","unstructured":"Rinaldi, G.: Rudy. http:\/\/www-user.tu-chemnitz.de\/ (1998)"},{"issue":"2","key":"2195_CR35","doi-asserted-by":"publisher","first-page":"1641","DOI":"10.1109\/TPWRS.2020.3044501","volume":"36","author":"J Sliwak","year":"2021","unstructured":"Sliwak, J., Andersen, E.D., Anjos, M.F., L\u00e9tocart, L., Traversi, E.: A clique merging algorithm to solve semidefinite relaxations of optimal power flow problems. IEEE Trans. Power Syst. 36(2), 1641\u20131644 (2021)","journal-title":"IEEE Trans. Power Syst."},{"issue":"3","key":"2195_CR36","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1137\/0213035","volume":"13","author":"R Tarjan","year":"1984","unstructured":"Tarjan, R., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput. 13(3), 566\u2013579 (1984)","journal-title":"SIAM J. Comput."},{"key":"2195_CR37","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/j.envsoft.2017.01.006","volume":"90","author":"J Teng","year":"2017","unstructured":"Teng, J., Jakeman, A., Vaze, J., Croke, B., Dutta, D., Kim, S.: Flood inundation modelling: A review of methods, recent advances and uncertainty analysis. Environ. Modell. Softw. 90, 201\u2013216 (2017)","journal-title":"Environ. Modell. Softw."},{"issue":"4","key":"2195_CR38","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1561\/2400000006","volume":"1","author":"L Vandenberghe","year":"2014","unstructured":"Vandenberghe, L., Andersen, M.S.: Chordal graphs and semidefinite optimization. Found. Trends Optim. 1(4), 241\u2013443 (2014)","journal-title":"Found. Trends Optim."},{"issue":"1","key":"2195_CR39","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1137\/050623802","volume":"17","author":"H Waki","year":"2006","unstructured":"Waki, H., Kim, S., Kojima, M., Muramatsu, M.: Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity. SIAM J. Optim. 17(1), 218\u2013242 (2006)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"2195_CR40","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/s10957-021-01975-z","volume":"192","author":"J Wang","year":"2022","unstructured":"Wang, J., Magron, V.: Exploiting sparsity in complex polynomial optimization. J. Optim. Theory App. 192(1), 335\u2013359 (2022)","journal-title":"J. Optim. Theory App."},{"issue":"1","key":"2195_CR41","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1137\/20M1323564","volume":"31","author":"J Wang","year":"2021","unstructured":"Wang, J., Magron, V., Lasserre, J.B.: Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension. SIAM J. Optim. 31(1), 114\u2013141 (2021)","journal-title":"SIAM J. Optim."},{"key":"2195_CR42","doi-asserted-by":"crossref","unstructured":"Wang, J., Magron, V., Lasserre, J.B., Mai, N.H.A.: CS-TSSOS: Correlative and term sparsity for large scale polynomial optimization. arXiv:2005.02828 (2021)","DOI":"10.1145\/3569709"},{"issue":"1","key":"2195_CR43","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/s10107-020-01516-y","volume":"188","author":"RY Zhang","year":"2021","unstructured":"Zhang, R.Y., Lavaei, J.: Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion. Math. Program. Ser. A 188(1), 351\u2013393 (2021)","journal-title":"Math. Program. Ser. A"},{"issue":"1","key":"2195_CR44","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/s10107-019-01366-3","volume":"180","author":"Y Zheng","year":"2020","unstructured":"Zheng, Y., Fantuzzi, G., Papachristodoulou, A., Goulart, P., Wynn, A.: Chordal decomposition in operator-splitting methods for sparse semidefinite programs. Math. Program. Ser. A 180(1), 489\u2013532 (2020)","journal-title":"Math. Program. Ser. A"}],"container-title":["Journal of Optimization Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-023-02195-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10957-023-02195-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-023-02195-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,18]],"date-time":"2023-05-18T13:09:32Z","timestamp":1684415372000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10957-023-02195-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,20]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["2195"],"URL":"https:\/\/doi.org\/10.1007\/s10957-023-02195-3","relation":{},"ISSN":["0022-3239","1573-2878"],"issn-type":[{"type":"print","value":"0022-3239"},{"type":"electronic","value":"1573-2878"}],"subject":[],"published":{"date-parts":[[2023,3,20]]},"assertion":[{"value":"30 May 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 March 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 March 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}