{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T00:50:14Z","timestamp":1790643014586,"version":"4.1.0"},"reference-count":49,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N000141612889"],"award-info":[{"award-number":["N000141612889"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002848","name":"Comisi\u00f3n Nacional de Investigaci\u00f3n Cient\u00edfica y Tecnol\u00f3gica","doi-asserted-by":"publisher","award":["72130388"],"award-info":[{"award-number":["72130388"]}],"id":[{"id":"10.13039\/501100002848","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>We present a class of linear programming approximations for polynomial optimization problems that take advantage of structured sparsity given by a graph theoretical parameter, the tree-width. We consider two schemes that use this feature to produce provably good solutions. First we study problems whose system of constraints exhibits small tree-width, and we show that for any desired tolerance there is a linear programming approximation of polynomial size. Second, we consider problems where an existing sparse network is used to define variables and constraints of a polynomial optimization problem. In important applications, in spite of the structural sparsity of the network, a direct formulation may still be dense. Nevertheless, we show how to obtain polynomial tractability of an approximation scheme in such a case as well.<\/jats:p>","DOI":"10.1137\/15m1054079","type":"journal-article","created":{"date-parts":[[2018,4,10]],"date-time":"2018-04-10T14:48:58Z","timestamp":1523371738000},"page":"1121-1150","source":"Crossref","is-referenced-by-count":33,"title":["LP Formulations for Polynomial Optimization Problems"],"prefix":"10.1137","volume":"28","author":[{"given":"Daniel","family":"Bienstock","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gonzalo","family":"Mun\u0342oz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,4,10]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1002\/aic.690100626"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01934985"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/0608024"},{"key":"atypb4","unstructured":"S. Arnborg and A. Proskurowski,\n                      Linear Time Algorithms for NP-hard Problems on Graphs Embedded in $k$-trees\n                      , Tech. Report TRITA-NA-8404, The Royal Institute of Technology, Stockholm, 1984."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90039-3"},{"key":"atypb6","unstructured":"U. Bertele and F. Brioschi,\n                      Nonserial Dynamic Programming\n                      , Academic Press, 1972."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.21314\/JCF.2007.168"},{"key":"atypb8","first-page":"481","volume":"7","author":"Bienstock D.","year":"1995","journal-title":"Handb. Oper. Res. Management Sci."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2004.03.002"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-19488-6_110"},{"key":"atypb11","unstructured":"S. Bose, D. F. Gayme, S. H. Low, and K. M. Chandy,\n                      Quadratically Constrained Quadratic Programs on Acyclic Graphs with Application to Power Flow\n                      , preprint,http:\/\/arxiv.org\/abs\/1203.5599, 2012."},{"key":"atypb12","first-page":"350","author":"Braun G.","year":"2016","journal-title":"Springer International Publishing"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1080\/00207168908803783"},{"key":"atypb14","unstructured":"V. Chandrasekaran, N. Srebro, and P. Harsha,\n                      Complexity of Inference in Graphical Models\n                      , in Proc. 24th Conference on Uncertainty in Artificial Intelligence, 2008."},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72792-7_13"},{"key":"atypb16","first-page":"337","author":"Dash S.","year":"2007","journal-title":"Springer"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/100790835"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.05.011"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0825-6"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/140976650"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(89)90037-4"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90054-8"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4225"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1965.15.835"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.22.4.455"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1080\/02331939208843796"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/s00013-007-2234-z"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1137\/110836183"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1090.0348"},{"key":"atypb30","doi-asserted-by":"crossref","unstructured":"T. Koch, B. Hiller, M. E. Pfetsch, and L. Schewe, eds.\n                      Evaluating Gas Network Capacities\n                      , SIAM, Philadelphia, 2015,https:\/\/doi.org\/10.1137\/1.9781611973693.","DOI":"10.1137\/1.9781611973693"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0554-3"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1137\/05064504X"},{"key":"atypb33","unstructured":"J. Lasserre, K.C. Toh, and S. Yang,\n                      A Bounded Degree SOS Hierarchy for Polynomial Optimization\n                      , preprint,https:\/\/arxiv.org\/abs\/1501.06126, 2015."},{"key":"atypb34","first-page":"157","volume":"149","author":"Laurent M.","year":"2009","journal-title":"IMA"},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"S. L. Lauritzen,\n                      Graphical Models\n                      , Oxford University Press, 1996.","DOI":"10.1093\/oso\/9780198522195.001.0001"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1109\/TPWRS.2011.2160974"},{"key":"atypb37","unstructured":"G. Mun\u0342oz,\n                      Integer Programming Techniques for Polynomial Optimization\n                      , Ph.D. dissertation, Columbia University, 2017."},{"key":"atypb38","unstructured":"G. Nemhauser,\n                      Introduction to Dynamic Programming\n                      , Wiley, 1966."},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-013-0680-x"},{"key":"atypb40","first-page":"133","author":"Pearl J.","year":"1982","journal-title":"Proceedings of the National Conference on Artificial Intelligence"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90013-3"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1137\/0403036"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-011-9757-3"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(97)00013-8"},{"key":"atypb46","unstructured":"M. Wainwright and M. Jordan,\n                      Treewidth-Based Conditions for Exactness of the Sherali-Adams and Lasserre Relaxations\n                      , Tech. Report 671, University of California, 2004."},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1561\/2200000001"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1137\/050623802"},{"key":"atypb49","unstructured":"M. Zuckerberg,\n                      A Set Theoretic Approach to Lifting Procedures for 0,1 Integer Programming\n                      , Ph.D. dissertation, Columbia University, 2009,http:\/\/www.columbia.edu\/~dano\/theses\/theses.html."}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/15M1054079","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:02:58Z","timestamp":1787338978000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/15M1054079"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":49,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/15M1054079"],"URL":"https:\/\/doi.org\/10.1137\/15m1054079","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}