{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T05:26:35Z","timestamp":1787289995844,"version":"build-2736575974"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T00:00:00Z","timestamp":1783728000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T00:00:00Z","timestamp":1783728000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004837","name":"Ministerio de Ciencia e Innovaci\u00f3n","doi-asserted-by":"publisher","award":["PID2020-114594GB-C21"],"award-info":[{"award-number":["PID2020-114594GB-C21"]}],"id":[{"id":"10.13039\/501100004837","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004837","name":"Ministerio de Ciencia e Innovaci\u00f3n","doi-asserted-by":"publisher","award":["PID2020-114594GB-C21"],"award-info":[{"award-number":["PID2020-114594GB-C21"]}],"id":[{"id":"10.13039\/501100004837","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100016970","name":"Consejer\u00eda de Econom\u00eda, Conocimiento, Empresas y Universidad, Junta de Andaluc\u00eda","doi-asserted-by":"publisher","award":["C-EXP-139-UGR23"],"award-info":[{"award-number":["C-EXP-139-UGR23"]}],"id":[{"id":"10.13039\/100016970","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100016970","name":"Consejer\u00eda de Econom\u00eda, Conocimiento, Empresas y Universidad, Junta de Andaluc\u00eda","doi-asserted-by":"publisher","award":["C-EXP-139-UGR23"],"award-info":[{"award-number":["C-EXP-139-UGR23"]}],"id":[{"id":"10.13039\/100016970","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100016970","name":"Consejer\u00eda de Econom\u00eda, Conocimiento, Empresas y Universidad, Junta de Andaluc\u00eda","doi-asserted-by":"publisher","award":["RED2022-134149-T"],"award-info":[{"award-number":["RED2022-134149-T"]}],"id":[{"id":"10.13039\/100016970","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004837","name":"Ministerio de Ciencia e Innovaci\u00f3n","doi-asserted-by":"publisher","award":["IMAG-Mar\u00eda de Maeztu grant CEX2020-001105-M"],"award-info":[{"award-number":["IMAG-Mar\u00eda de Maeztu grant CEX2020-001105-M"]}],"id":[{"id":"10.13039\/501100004837","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004837","name":"Ministerio de Ciencia e Innovaci\u00f3n","doi-asserted-by":"publisher","award":["PID2024-155024-2"],"award-info":[{"award-number":["PID2024-155024-2"]}],"id":[{"id":"10.13039\/501100004837","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":[[2026,8]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    In this paper, we introduce a unified definition of\n                    <jats:italic>mediated graphs<\/jats:italic>\n                    , a combinatorial structure that underlies several constructions in polynomial and conic optimization. We investigate their geometric and algebraic properties and study extremal mediated graphs under the partial order induced by the cardinality of their vertex sets. We develop mixed-integer linear formulations that enable the exact computation of these graphs, which are typically difficult to obtain by direct enumeration. We show that mediated graphs play a crucial role in SOS and SONC decompositions of polynomials, as well as in second-order cone representations of convex cones, thereby providing new modeling tools with a direct impact on conic optimization. An extensive computational study demonstrates the effectiveness and scalability of the proposed methods.\n                  <\/jats:p>","DOI":"10.1007\/s10957-026-03048-5","type":"journal-article","created":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T05:40:48Z","timestamp":1783748448000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Structure and Computation of Extremal Mediated Graphs with Applications to Conic Optimization"],"prefix":"10.1007","volume":"210","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7762-6461","authenticated-orcid":false,"given":"V\u00edctor","family":"Blanco","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4224-3655","authenticated-orcid":false,"given":"Miguel","family":"Mart\u00ednez-Ant\u00f3n","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,7,11]]},"reference":[{"issue":"3","key":"3048_CR1","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/s13675-018-0103-0","volume":"6","author":"C Buchheim","year":"2018","unstructured":"Buchheim, C., Kurtz, J.: Robust combinatorial optimization under convex and discrete cost uncertainty. EURO Journal on Computational Optimization 6(3), 211\u2013238 (2018)","journal-title":"EURO Journal on Computational Optimization"},{"issue":"4\u20135","key":"3048_CR2","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1080\/10556780903057341","volume":"24","author":"S Burer","year":"2009","unstructured":"Burer, S., Chen, J.: A $$p$$-cone sequential relaxation procedure for $$0$$-$$1$$ integer programs. Optimization Methods & Software 24(4\u20135), 523\u2013548 (2009)","journal-title":"Optimization Methods & Software"},{"issue":"2","key":"3048_CR3","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1287\/moor.26.2.193.10561","volume":"26","author":"A Ben-Tal","year":"2001","unstructured":"Ben-Tal, A., Nemirovski, A.: On polyhedral approximations of the second-order cone. Math. Oper. Res. 26(2), 193\u2013205 (2001)","journal-title":"Math. Oper. Res."},{"key":"3048_CR4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2025.101979","volume":"91","author":"V Blanco","year":"2025","unstructured":"Blanco, V., Magron, V., Mart\u00ednez-Ant\u00f3n, M.: On the complexity of $$p$$-order cone programs. J. Complex. 91, 101979 (2025)","journal-title":"J. Complex."},{"issue":"3","key":"3048_CR5","doi-asserted-by":"publisher","first-page":"3088","DOI":"10.1137\/23M1617205","volume":"4","author":"V Blanco","year":"2024","unstructured":"Blanco, V., Mart\u00ednez-Ant\u00f3n, M.: On minimal extended representations of generalized power cones. SIAM J. Optim. 4(3), 3088\u20133111 (2024)","journal-title":"SIAM J. Optim."},{"key":"3048_CR6","doi-asserted-by":"publisher","DOI":"10.1016\/j.omega.2023.102956","volume":"122","author":"V Blanco","year":"2024","unstructured":"Blanco, V., Mart\u00ednez-Ant\u00f3n, M.: Optimal coverage-based placement of static leak detection devices for pipeline water supply networks. Omega 122, 102956 (2024)","journal-title":"Omega"},{"issue":"4","key":"3048_CR7","doi-asserted-by":"publisher","first-page":"2226","DOI":"10.1111\/itor.12993","volume":"29","author":"V Blanco","year":"2022","unstructured":"Blanco, V., Puerto, J.: On hub location problems in geographically flexible networks. Int. Trans. Oper. Res. 29(4), 2226\u20132249 (2022)","journal-title":"Int. Trans. Oper. Res."},{"issue":"3","key":"3048_CR8","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/s10589-014-9638-z","volume":"58","author":"V Blanco","year":"2014","unstructured":"Blanco, V., Puerto, J., ElHaj-BenAli, S.: Revisiting several problems and algorithms in continuous location with $$\\ell _\\tau $$ norms. Comput. Optim. Appl. 58(3), 563\u2013595 (2014)","journal-title":"Comput. Optim. Appl."},{"issue":"1","key":"3048_CR9","doi-asserted-by":"publisher","first-page":"536","DOI":"10.1137\/16M1086303","volume":"1","author":"M Dressler","year":"2017","unstructured":"Dressler, M., Iliman, S., De Wolff, T.: A positivstellensatz for sums of nonnegative circuit polynomials. SIAM Journal on Applied Algebra and Geometry 1(1), 536\u2013555 (2017)","journal-title":"SIAM Journal on Applied Algebra and Geometry"},{"issue":"1","key":"3048_CR10","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/s00186-022-00773-1","volume":"95","author":"E Gaar","year":"2022","unstructured":"Gaar, E., Siebenhofer, M., Wiegele, A.: An SDP-based approach for computing the stability number of a graph. Math. Methods Oper. Res. 95(1), 141\u2013161 (2022)","journal-title":"Math. Methods Oper. Res."},{"issue":"1","key":"3048_CR11","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/BF02614315","volume":"79","author":"MX Goemans","year":"1997","unstructured":"Goemans, M.X.: Semidefinite programming in combinatorial optimization. Math. Program. 79(1), 143\u2013161 (1997)","journal-title":"Math. Program."},{"issue":"6","key":"3048_CR12","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":"3048_CR13","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1016\/j.jsc.2020.07.013","volume":"109","author":"J Hartzer","year":"2022","unstructured":"Hartzer, J., R\u00f6hrig, O., de Wolff, T., Y\u00fcr\u00fck, O.: Initial steps in the classification of maximal mediated sets. J. Symb. Comput. 109, 404\u2013425 (2022)","journal-title":"J. Symb. Comput."},{"key":"3048_CR14","doi-asserted-by":"publisher","DOI":"10.1142\/q0252","volume-title":"The Moment-SOS Hierarchy","author":"D Henrion","year":"2020","unstructured":"Henrion, D., Korda, M., Lasserre, J.B.: The Moment-SOS Hierarchy. World Scientific, Europe (2020)"},{"key":"3048_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s40687-016-0052-2","volume":"3","author":"S Iliman","year":"2016","unstructured":"Iliman, S., De Wolff, T.: Amoebas, nonnegative polynomials and sums of squares supported on circuits. Research in the Mathematical Sciences 3, 1\u201335 (2016)","journal-title":"Research in the Mathematical Sciences"},{"issue":"2","key":"3048_CR16","doi-asserted-by":"publisher","first-page":"1128","DOI":"10.1137\/140962425","volume":"26","author":"S Iliman","year":"2016","unstructured":"Iliman, S., De Wolff, T.: Lower bounds for polynomials with simplex Newton polytopes based on geometric programming. SIAM J. Optim. 26(2), 1128\u20131146 (2016)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"3048_CR17","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1137\/S1052623400366802","volume":"11","author":"JB Lasserre","year":"2001","unstructured":"Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3), 796\u2013817 (2001)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"3048_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz, L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Theory 25(1), 1\u20137 (1979)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"3048_CR19","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1016\/j.jsc.2022.08.002","volume":"115","author":"V Magron","year":"2023","unstructured":"Magron, V., Wang, J.: SONC optimization and exact nonnegativity certificates via second-order cone programming. J. Symb. Comput. 115, 346\u2013370 (2023)","journal-title":"J. Symb. Comput."},{"issue":"2","key":"3048_CR20","doi-asserted-by":"publisher","first-page":"164","DOI":"10.15807\/jorsj.46.164","volume":"46","author":"M Muramatsu","year":"2003","unstructured":"Muramatsu, M., Suzuki, T.: A new second-order cone programming relaxation for max-cut problems. Journal of the Operations Research Society of Japan 46(2), 164\u2013177 (2003)","journal-title":"Journal of the Operations Research Society of Japan"},{"key":"3048_CR21","unstructured":"O\u2019Donnell, R.: SOS is not obviously automatizable, even approximately. In: Papadimitriou, C.H. (ed.): 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), Leibniz International Proceedings in Informatics (LIPIcs), vol. 67, pp. 59:1-59:10. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2017)"},{"key":"3048_CR22","doi-asserted-by":"crossref","unstructured":"Orecchia, L., Vishnoi, N.K.: Towards an SDP-based approach to spectral methods: a nearly-linear-time algorithm for graph partitioning and decomposition. In: Proceedings of the 2011 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 532\u2013545. (2011)","DOI":"10.1137\/1.9781611973082.42"},{"key":"3048_CR23","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s10107-003-0387-5","volume":"96","author":"PA Parrilo","year":"2003","unstructured":"Parrilo, P.A.: Semidefinite programming relaxations for semialgebraic problems. Math. Program. 96, 293\u2013320 (2003)","journal-title":"Math. Program."},{"issue":"2\u20133","key":"3048_CR24","doi-asserted-by":"publisher","first-page":"307","DOI":"10.3166\/ejc.9.307-321","volume":"9","author":"PA Parrilo","year":"2003","unstructured":"Parrilo, P.A., Lall, S.: Semidefinite programming relaxations and algebraic optimization in control. Eur. J. Control. 9(2\u20133), 307\u2013321 (2003)","journal-title":"Eur. J. Control."},{"key":"3048_CR25","doi-asserted-by":"crossref","unstructured":"Pauwels, E., Henrion, D., Lasserre, J.B.: Positivity certificates in optimal control. Geometric and Numerical Foundations of Movements, pp. 113\u2013131. (2017)","DOI":"10.1007\/978-3-319-51547-2_6"},{"issue":"7","key":"3048_CR26","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpaa.2020.106608","volume":"225","author":"V Powers","year":"2021","unstructured":"Powers, V., Reznick, B.: A note on mediated simplices. J. Pure Appl. Algebra 225(7), 106608 (2021)","journal-title":"J. Pure Appl. Algebra"},{"issue":"3","key":"3048_CR27","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/BF01442738","volume":"283","author":"B Reznick","year":"1989","unstructured":"Reznick, B.: Forms derived from the arithmetic-geometric inequality. Math. Ann. 283(3), 431\u2013464 (1989)","journal-title":"Math. Ann."},{"key":"3048_CR28","doi-asserted-by":"crossref","unstructured":"Sotirov, R.: SDP relaxations for some combinatorial optimization problems. In: Anjos, M.F., Lasserre, J.B. (eds.) Handbook on Semidefinite, Conic and Polynomial Optimization, pp. 795\u2013819. Springer, New York (2012)","DOI":"10.1007\/978-1-4614-0769-0_27"},{"issue":"2","key":"3048_CR29","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1137\/20M1313969","volume":"6","author":"J Wang","year":"2022","unstructured":"Wang, J.: Nonnegative polynomials and circuit polynomials. SIAM Journal on Applied Algebra and Geometry 6(2), 111\u2013133 (2022)","journal-title":"SIAM Journal on Applied Algebra and Geometry"},{"issue":"2","key":"3048_CR30","doi-asserted-by":"publisher","first-page":"1490","DOI":"10.1137\/22M1531257","volume":"34","author":"J Wang","year":"2024","unstructured":"Wang, J.: Weighted geometric mean, minimum mediated set, and optimal simple second-order cone representation. SIAM J. Optim. 34(2), 1490\u20131514 (2024)","journal-title":"SIAM J. Optim."}],"container-title":["Journal of Optimization Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-026-03048-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10957-026-03048-5","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-026-03048-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T05:08:54Z","timestamp":1787288934000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10957-026-03048-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,11]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,8]]}},"alternative-id":["3048"],"URL":"https:\/\/doi.org\/10.1007\/s10957-026-03048-5","relation":{},"ISSN":["0022-3239","1573-2878"],"issn-type":[{"value":"0022-3239","type":"print"},{"value":"1573-2878","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,11]]},"assertion":[{"value":"4 May 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 June 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 July 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare that they have no competing interests.","order":1,"name":"Ethics","label":"Competing Interests","group":{"name":"EthicsHeading","label":"Declarations"}}],"article-number":"24"}}