{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,11]],"date-time":"2025-11-11T13:40:04Z","timestamp":1762868404462,"version":"3.37.3"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T00:00:00Z","timestamp":1609718400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T00:00:00Z","timestamp":1609718400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2021,9]]},"DOI":"10.1007\/s10898-020-00973-1","type":"journal-article","created":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T02:02:48Z","timestamp":1609725768000},"page":"3-22","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Learning chordal extensions"],"prefix":"10.1007","volume":"81","author":[{"given":"Defeng","family":"Liu","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9269-633X","authenticated-orcid":false,"given":"Andrea","family":"Lodi","sequence":"additional","affiliation":[]},{"given":"Mathieu","family":"Tanneau","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,1,4]]},"reference":[{"key":"973_CR1","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0024-3795(88)90240-6","volume":"107","author":"J Agler","year":"1988","unstructured":"Agler, J., Helton, W., McCullough, S., Rodman, L.: Positive semidefinite matrices with a given sparsity pattern. Linear Algebra Appl. 107, 101\u2013149 (1988). https:\/\/doi.org\/10.1016\/0024-3795(88)90240-6","journal-title":"Linear Algebra Appl."},{"key":"973_CR2","doi-asserted-by":"crossref","unstructured":"Bagnell, J., Chestnutt, J., Bradley, D.M., Ratliff, N.D.: Boosting structured prediction for imitation learning. In: Advances in Neural Information Processing Systems, pp. 1153\u20131160 (2007)","DOI":"10.7551\/mitpress\/7503.003.0149"},{"key":"973_CR3","unstructured":"Bengio, Y., Lodi, A., Prouvost, A.: Machine learning for combinatorial optimization: a methodological tour d\u2019horizon. arXiv preprint arXiv:1811.06128 (2018)"},{"issue":"2","key":"973_CR4","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1287\/opre.2018.1783","volume":"67","author":"D Bergman","year":"2019","unstructured":"Bergman, D., Cardonha, C.H., Cire, A.A., Raghunathan, A.U.: On the minimum chordal completion polytope. Oper. Res. 67(2), 532\u2013547 (2019). https:\/\/doi.org\/10.1287\/opre.2018.1783","journal-title":"Oper. Res."},{"issue":"1","key":"973_CR5","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1287\/opre.50.1.3.17780","volume":"50","author":"RE Bixby","year":"2002","unstructured":"Bixby, R.E.: Solving real-world linear programs: a decade and more of progress. Oper. Res. 50(1), 3\u201315 (2002). https:\/\/doi.org\/10.1287\/opre.50.1.3.17780","journal-title":"Oper. Res."},{"issue":"1","key":"973_CR6","doi-asserted-by":"publisher","first-page":"1:1","DOI":"10.1145\/2049662.2049663","volume":"38","author":"TA Davis","year":"2011","unstructured":"Davis, T.A., Hu, Y.: The university of florida sparse matrix collection. ACM Trans. Math. Softw. 38(1), 1:1\u20131:25 (2011). https:\/\/doi.org\/10.1145\/2049662.2049663","journal-title":"ACM Trans. Math. Softw."},{"key":"973_CR7","unstructured":"Duvenaud, D.K., Maclaurin, D., Iparraguirre, J., Bombarell, R., Hirzel, T., Aspuru-Guzik, A., Adams, R.P.: Convolutional networks on graphs for learning molecular fingerprints. In: Advances in Neural Information Processing Systems, pp. 2224\u20132232 (2015)"},{"issue":"1","key":"973_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-013-9776-1","volume":"71","author":"FV Fomin","year":"2015","unstructured":"Fomin, F.V., Philip, G., Villanger, Y.: Minimum fill-in of sparse graphs: Kernelization and approximation. Algorithmica 71(1), 1\u201320 (2015). https:\/\/doi.org\/10.1007\/s00453-013-9776-1","journal-title":"Algorithmica"},{"issue":"3","key":"973_CR9","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."},{"key":"973_CR10","doi-asserted-by":"crossref","unstructured":"Garstka, M., Cannon, M., Goulart, P.: A Clique Graph Based Merging Strategy for Decomposable SDPS (2019)","DOI":"10.1016\/j.ifacol.2020.12.1255"},{"key":"973_CR11","unstructured":"Gasse, M., Ch\u00e9telat, D., Ferroni, N., Charlin, L., Lodi, A.: Exact combinatorial optimization with graph convolutional neural networks. arXiv preprint arXiv:1906.01629 (2019)"},{"issue":"2","key":"973_CR12","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1137\/0710032","volume":"10","author":"A George","year":"1973","unstructured":"George, A.: Nested dissection of a regular finite element mesh. SIAM J. Numer. Anal. 10(2), 345\u2013363 (1973). https:\/\/doi.org\/10.1137\/0710032","journal-title":"SIAM J. Numer. Anal."},{"issue":"1","key":"973_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/1031001","volume":"31","author":"A George","year":"1989","unstructured":"George, A., Liu, J.W.: The evolution of the minimum degree ordering algorithm. SIAM Rev. 31(1), 1\u201319 (1989). https:\/\/doi.org\/10.1137\/1031001","journal-title":"SIAM Rev."},{"key":"973_CR14","unstructured":"Glorot, X., Bengio, Y.: Understanding the difficulty of training deep feedforward neural networks. In: Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 249\u2013256 (2010)"},{"key":"973_CR15","unstructured":"Gori, M., Monfardini, G., Scarselli, F.: A new model for learning in graph domains. In: Proceedings of 2005 IEEE International Joint Conference on Neural Networks, 2005., vol.\u00a02, pp. 729\u2013734. IEEE (2005)"},{"issue":"9","key":"973_CR16","doi-asserted-by":"publisher","first-page":"1191","DOI":"10.1016\/S0167-8191(03)00099-1","volume":"29","author":"A Guermouche","year":"2003","unstructured":"Guermouche, A., L\u2019Excellent, J.Y., Utard, G.: Impact of reordering on the memory of a multifrontal solver. Parallel Comput. Parallel Matrix Algorithms Appl. 29(9), 1191\u20131218 (2003). https:\/\/doi.org\/10.1016\/S0167-8191(03)00099-1","journal-title":"Parallel Comput. Parallel Matrix Algorithms Appl."},{"key":"973_CR17","unstructured":"Hamilton, W., Ying, Z., Leskovec, J.: Inductive representation learning on large graphs. In: Advances in Neural Information Processing Systems, pp. 1024\u20131034 (2017)"},{"key":"973_CR18","unstructured":"Hamilton, W.L., Ying, R., Leskovec, J.: Representation learning on graphs: methods and applications. arXiv preprint arXiv:1709.05584 (2017)"},{"key":"973_CR19","unstructured":"Howard, R.A.: Dynamic programming and Markov processes. (1960)"},{"key":"973_CR20","unstructured":"Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2016)"},{"key":"973_CR21","unstructured":"Kullback, S.: Information theory and statistics. Courier Corporation (1997)"},{"key":"973_CR22","unstructured":"Li, Z., Chen, Q., Koltun, V.: Combinatorial optimization with graph convolutional networks and guided tree search. In: Advances in Neural Information Processing Systems, pp. 539\u2013548 (2018)"},{"issue":"1","key":"973_CR23","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1137\/0611010","volume":"11","author":"JW Liu","year":"1990","unstructured":"Liu, J.W.: The role of elimination trees in sparse factorization. SIAM J. Matrix Anal. Appl. 11(1), 134\u2013172 (1990). https:\/\/doi.org\/10.1137\/0611010","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"973_CR24","doi-asserted-by":"crossref","unstructured":"Majumdar, A., Hall, G., Ahmadi, A.A.: A survey of recent scalability improvements for semidefinite programming with applications in machine learning, control, and robotics. arXiv preprint arXiv:1908.05209 (2019)","DOI":"10.1146\/annurev-control-091819-074326"},{"issue":"3","key":"973_CR25","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1287\/mnsc.3.3.255","volume":"3","author":"HM Markowitz","year":"1957","unstructured":"Markowitz, H.M.: The elimination form of the inverse and its application to linear programming. Manag. Sci. 3(3), 255\u2013269 (1957). https:\/\/doi.org\/10.1287\/mnsc.3.3.255","journal-title":"Manag. Sci."},{"issue":"2","key":"973_CR26","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/s10107-002-0351-9","volume":"95","author":"K Nakata","year":"2003","unstructured":"Nakata, K., Fujisawa, K., Fukuda, M., Kojima, M., Murota, K.: Exploiting sparsity in semidefinite programming via matrix completion II: implementation and numerical results. Math. Progr. 95(2), 303\u2013327 (2003)","journal-title":"Math. Progr."},{"key":"973_CR27","doi-asserted-by":"crossref","unstructured":"Pan, Y., Cheng, C.A., Saigol, K., Lee, K., Yan, X., Theodorou, E., Boots, B.: Agile autonomous driving using end-to-end deep imitation learning. In: Robotics: Science and Systems (2018)","DOI":"10.15607\/RSS.2018.XIV.056"},{"issue":"1","key":"973_CR28","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/s10514-009-9121-3","volume":"27","author":"ND Ratliff","year":"2009","unstructured":"Ratliff, N.D., Silver, D., Bagnell, J.A.: Learning to search: functional gradient techniques for imitation learning. Auton. Robots 27(1), 25\u201353 (2009)","journal-title":"Auton. Robots"},{"key":"973_CR29","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/B978-1-4832-3187-7.50018-0","volume-title":"Graph Theory and Computing","author":"DJ Rose","year":"1972","unstructured":"Rose, D.J.: A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. Graph Theory and Computing, pp. 183\u2013217. Elsevier, New York (1972)"},{"key":"973_CR30","unstructured":"Ross, S., Bagnell, D.: Efficient reductions for imitation learning. In: Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pp. 661\u2013668 (2010)"},{"key":"973_CR31","unstructured":"Ross, S., Gordon, G., Bagnell, D.: A reduction of imitation learning and structured prediction to no-regret online learning. In: Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 627\u2013635 (2011)"},{"issue":"1","key":"973_CR32","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1287\/ijoc.10.1.107","volume":"10","author":"E Rothberg","year":"1998","unstructured":"Rothberg, E., Hendrickson, B.: Sparse matrix ordering methods for interior point linear programming. INFORMS J. Comput. 10(1), 107\u2013113 (1998). https:\/\/doi.org\/10.1287\/ijoc.10.1.107","journal-title":"INFORMS J. Comput."},{"issue":"6","key":"973_CR33","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/S1364-6613(99)01327-3","volume":"3","author":"S Schaal","year":"1999","unstructured":"Schaal, S.: Is imitation learning the route to humanoid robots? Trends Cognit. Sci. 3(6), 233\u2013242 (1999)","journal-title":"Trends Cognit. Sci."},{"key":"973_CR34","doi-asserted-by":"crossref","unstructured":"Silver, D., Bagnell, J., Stentz, A.: High performance outdoor navigation from overhead data using imitation learning. Robotics: Science and Systems IV, Zurich, Switzerland (2008)","DOI":"10.15607\/RSS.2008.IV.034"},{"key":"973_CR35","unstructured":"Sliwak, J., Anjos, M., L\u00e9tocart, L., Maeght, J., Traversi, E.: Improving clique decompositions of semidefinite relaxations for optimal power flow problems. EasyChair Preprint no. 2546 (EasyChair, 2020)"},{"issue":"4","key":"973_CR36","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1561\/2400000006","volume":"1","author":"L Vandenberghe","year":"2015","unstructured":"Vandenberghe, L., Andersen, M.S., et al.: Chordal graphs and semidefinite optimization. Found. Trends\u00ae Optim. 1(4), 241\u2013433 (2015)","journal-title":"Found. Trends\u00ae Optim."},{"issue":"1\u20134","key":"973_CR37","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1080\/10556789908805759","volume":"11","author":"RJ Vanderbei","year":"1999","unstructured":"Vanderbei, R.J.: LOQO: an interior point code for quadratic programming. Optim. Methods Softw. 11(1\u20134), 451\u2013484 (1999). https:\/\/doi.org\/10.1080\/10556789908805759","journal-title":"Optim. Methods Softw."},{"key":"973_CR38","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971453","author":"S Wright","year":"1997","unstructured":"Wright, S.: Primal-dual interior-point methods. Soc. Ind. Appl. Math. (1997). https:\/\/doi.org\/10.1137\/1.9781611971453","journal-title":"Soc. Ind. Appl. Math."},{"issue":"1","key":"973_CR39","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1137\/0602010","volume":"2","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM J. Algebraic Discrete Methods 2(1), 77\u201379 (1981). https:\/\/doi.org\/10.1137\/0602010","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"973_CR40","unstructured":"Ying, Z., Bourgeois, D., You, J., Zitnik, M., Leskovec, J.: Gnnexplainer: Generating explanations for graph neural networks. In: H.\u00a0Wallach, H.\u00a0Larochelle, A.\u00a0Beygelzimer, F.\u00a0d\u2019Alch\u00e9 Buc, E.\u00a0Fox, R.\u00a0Garnett (eds.) Advances in Neural Information Processing Systems 32, pp. 9244\u20139255. Curran Associates, Inc. (2019)"},{"key":"973_CR41","doi-asserted-by":"crossref","unstructured":"Zheng, Y., Fantuzzi, G.: Sum-of-squares chordal decomposition of polynomial matrix inequalities. arXiv:2007.11410 [cs, eess, math] (2020)","DOI":"10.1007\/s10107-021-01728-w"},{"key":"973_CR42","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01366-3","author":"Y Zheng","year":"2019","unstructured":"Zheng, Y., Fantuzzi, G., Papachristodoulou, A., Goulart, P., Wynn, A.: Chordal decomposition in operator-splitting methods for sparse semidefinite programs. Math. Progr. (2019). https:\/\/doi.org\/10.1007\/s10107-019-01366-3","journal-title":"Math. Progr."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-020-00973-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-020-00973-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-020-00973-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,16]],"date-time":"2023-10-16T18:56:14Z","timestamp":1697482574000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-020-00973-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,4]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["973"],"URL":"https:\/\/doi.org\/10.1007\/s10898-020-00973-1","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"type":"print","value":"0925-5001"},{"type":"electronic","value":"1573-2916"}],"subject":[],"published":{"date-parts":[[2021,1,4]]},"assertion":[{"value":"6 October 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 November 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 January 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}