{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:14Z","timestamp":1740109274348,"version":"3.37.3"},"reference-count":65,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,9,15]],"date-time":"2020-09-15T00:00:00Z","timestamp":1600128000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,9,15]],"date-time":"2020-09-15T00:00:00Z","timestamp":1600128000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CMMI-1452463"],"award-info":[{"award-number":["CMMI-1452463"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,2]]},"DOI":"10.1007\/s10107-020-01563-5","type":"journal-article","created":{"date-parts":[[2020,9,15]],"date-time":"2020-09-15T12:02:39Z","timestamp":1600171359000},"page":"559-594","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["New limits of treewidth-based tractability in optimization"],"prefix":"10.1007","volume":"191","author":[{"given":"Yuri","family":"Faenza","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9003-441X","authenticated-orcid":false,"given":"Gonzalo","family":"Mu\u00f1oz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Pokutta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,9,15]]},"reference":[{"issue":"1","key":"1563_CR1","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.orl.2018.12.001","volume":"47","author":"P Aboulker","year":"2019","unstructured":"Aboulker, P., Fiorini, S., Huynh, T., Macchia, M., Seif, J.: Extension complexity of the correlation polytope. Oper. Res. Lett. 47(1), 47\u201351 (2019)","journal-title":"Oper. Res. Lett."},{"key":"1563_CR2","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/BF01934985","volume":"25","author":"S Arnborg","year":"1985","unstructured":"Arnborg, S.: Efficient algorithms for combinatorial problems on graphs with bounded decomposability. A survey. BIT Numer. Math. 25, 2\u201323 (1985)","journal-title":"BIT Numer. Math."},{"key":"1563_CR3","unstructured":"Arnborg, S., Proskurowski, A.: Linear time algorithms for NP-hard problems on graphs embedded in k-trees. Tech. Rep. TRITA-NA-8404, The Royal Institute of Technology, Stockholm (1984)"},{"issue":"2","key":"1563_CR4","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. Algebr. Discret. Methods 8(2), 277\u2013284 (1987)","journal-title":"SIAM J. Algebr. Discret. Methods"},{"issue":"2","key":"1563_CR5","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms 12(2), 308\u2013340 (1991)","journal-title":"J. Algorithms"},{"key":"1563_CR6","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity\u2014A Modern Approach","author":"S Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational Complexity\u2014A Modern Approach. Cambridge University Press, Cambridge (2009)"},{"issue":"6\u20138","key":"1563_CR7","doi-asserted-by":"publisher","first-page":"588","DOI":"10.1016\/j.ipl.2015.02.005","volume":"115","author":"D Avis","year":"2015","unstructured":"Avis, D., Tiwary, H.R.: A generalization of extension complexity that captures p. Inf. Process. Lett. 115(6\u20138), 588\u2013593 (2015a)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"1563_CR8","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/s10107-014-0764-2","volume":"153","author":"D Avis","year":"2015","unstructured":"Avis, D., Tiwary, H.R.: On the extension complexity of combinatorial polytopes. Math. Program. 153(1), 95\u2013115 (2015b)","journal-title":"Math. Program."},{"key":"1563_CR9","doi-asserted-by":"crossref","unstructured":"Bazzi, A., Fiorini, S., Pokutta, S., Svensson, O.: No small linear program approximates vertex cover within a factor 2\u2013e. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, pp. 1123\u20131142 (2015)","DOI":"10.1109\/FOCS.2015.73"},{"key":"1563_CR10","doi-asserted-by":"crossref","unstructured":"Bazzi, A., Fiorini, S., Pokutta, S., Svensson, O.: No small linear program approximates vertex cover within a factor 2\u2013e. In: Mathematics of Operations Research (2018) (to appear)","DOI":"10.1287\/moor.2017.0918"},{"issue":"2","key":"1563_CR11","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/0196-6774(87)90039-3","volume":"8","author":"M Bern","year":"1987","unstructured":"Bern, M., Lawler, E., Wong, A.: Linear-time computation of optimal subgraphs of decomposable graphs. J. Algorithms 8(2), 216\u2013235 (1987)","journal-title":"J. Algorithms"},{"key":"1563_CR12","series-title":"Handbooks in Operations Research and Management Science","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1016\/S0927-0507(05)80125-2","volume-title":"Network Models","author":"D Bienstock","year":"1995","unstructured":"Bienstock, D., Langston, M.A.: Chapter 8 algorithmic implications of the graph minor theorem. In: Ball, M.O., Magnant, C.M., Nemhauser, G. (eds.) Network Models. Handbooks in Operations Research and Management Science, pp. 481\u2013502. Elsevier, New York (1995)"},{"issue":"2","key":"1563_CR13","doi-asserted-by":"publisher","first-page":"1121","DOI":"10.1137\/15M1054079","volume":"28","author":"D Bienstock","year":"2018","unstructured":"Bienstock, D., Mu\u00f1oz, G.: LP formulations for polynomial optimization problems. SIAM J. Optim. 28(2), 1121\u20131150 (2018)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1563_CR14","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.disopt.2004.03.002","volume":"1","author":"D Bienstock","year":"2004","unstructured":"Bienstock, D., \u00d6zbay, N.: Tree-width and the Sherali\u2013Adams operator. Discret. Optim. 1(1), 13\u201321 (2004)","journal-title":"Discret. Optim."},{"key":"1563_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/3-540-19488-6_110","volume-title":"Automata, Languages and Programming","author":"H Bodlaender","year":"1988","unstructured":"Bodlaender, H.: Dynamic programming on graphs with bounded treewidth. In: Lepist\u00f6, T., Salomaa, A. (eds.) Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 317, pp. 105\u2013118. Springer, Berlin (1988)"},{"issue":"3","key":"1563_CR16","doi-asserted-by":"publisher","first-page":"756","DOI":"10.1287\/moor.2014.0694","volume":"40","author":"G Braun","year":"2015","unstructured":"Braun, G., Fiorini, S., Pokutta, S., Steurer, D.: Approximation limits of linear programs (beyond hierarchies). Math. Oper. Res. 40(3), 756\u2013772 (2015)","journal-title":"Math. Oper. Res."},{"issue":"1\u20132","key":"1563_CR17","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/s10107-016-0989-3","volume":"160","author":"G Braun","year":"2016","unstructured":"Braun, G., Fiorini, S., Pokutta, S.: Average case polyhedral complexity of the maximum stable set problem. Math. Program. 160(1\u20132), 407\u2013431 (2016a). https:\/\/doi.org\/10.1007\/s10107-016-0989-3","journal-title":"Math. Program."},{"key":"1563_CR18","doi-asserted-by":"crossref","unstructured":"Braun, G., Pokutta, S., Roy, A.: Strong reductions for extended formulations. In: International Conference on Integer Programming and Combinatorial Optimization, Springer, New York, pp. 350\u2013361 (2016b)","DOI":"10.1007\/978-3-319-33461-5_29"},{"key":"1563_CR19","doi-asserted-by":"crossref","unstructured":"Bri\u00ebt, J., Dadush, D., Pokutta, S.: On the existence of 0\/1 polytopes with high semidefinite extension complexity. In: European Symposium on Algorithms, Springer, New York, pp. 217\u2013228 (2013)","DOI":"10.1007\/978-3-642-40450-4_19"},{"issue":"1","key":"1563_CR20","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/s10107-014-0785-x","volume":"153","author":"J Bri\u00ebt","year":"2015","unstructured":"Bri\u00ebt, J., Dadush, D., Pokutta, S.: On the existence of 0\/1 polytopes with high semidefinite extension complexity. Math. Program. 153(1), 179\u2013199 (2015)","journal-title":"Math. Program."},{"issue":"1\u20132","key":"1563_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1080\/00207168908803783","volume":"31","author":"DJ Brown","year":"1989","unstructured":"Brown, D.J., Fellows, M.R., Langston, M.A.: Polynomial-time self-reducibility: theoretical motivations and practical results. Int. J. Comput. Math. 31(1\u20132), 1\u20139 (1989)","journal-title":"Int. J. Comput. Math."},{"key":"1563_CR22","unstructured":"Chandrasekaran, V., Srebro, N., Harsha, P.: Complexity of inference in graphical models. In: Proceedings of the Twenty-Fourth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-08), AUAI Press, Corvallis, Oregon, pp. 70\u201378 (2008)"},{"issue":"5","key":"1563_CR23","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1145\/2820609","volume":"63","author":"C Chekuri","year":"2016","unstructured":"Chekuri, C., Chuzhoy, J.: Polynomial bounds for the grid-minor theorem. J. ACM (JACM) 63(5), 40 (2016)","journal-title":"J. ACM (JACM)"},{"key":"1563_CR24","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J.: Improved bounds for the excluded grid theorem (2016). ArXiv preprint arXiv:1602.02629","DOI":"10.1145\/2746539.2746551"},{"issue":"1","key":"1563_CR25","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. Comput."},{"key":"1563_CR26","doi-asserted-by":"crossref","unstructured":"Courcelle, B., Mosbah, M.: Monadic second-order evaluations on tree-decomposable graphs. In: International Workshop on Graph-Theoretic Concepts in Computer Science, Springer, New York, pp. 13\u201324 (1991)","DOI":"10.1007\/3-540-55121-2_2"},{"key":"1563_CR27","doi-asserted-by":"crossref","unstructured":"Cunningham, W.H,. Geelen, J.: On integer programming and the branch-width of the constraint matrix. In: International Conference on Integer Programming and Combinatorial Optimization, Springer, New York, pp. 158\u2013166 (2007)","DOI":"10.1007\/978-3-540-72792-7_13"},{"key":"1563_CR28","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1016\/0004-3702(89)90037-4","volume":"38","author":"R Dechter","year":"1989","unstructured":"Dechter, R., Pearl, J.: Tree clustering for constraint networks (research note). Artif. Intell. 38, 353\u2013366 (1989)","journal-title":"Artif. Intell."},{"key":"1563_CR29","series-title":"Graduate Texts in Mathematics","volume-title":"Graph Theory","author":"R Diestel","year":"2012","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, New York (2012)","edition":"4"},{"issue":"1","key":"1563_CR30","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/s10107-015-0922-1","volume":"153","author":"H Fawzi","year":"2015","unstructured":"Fawzi, H., Gouveia, J., Parrilo, P.A., Robinson, R.Z., Thomas, R.R.: Positive semidefinite rank. Math. Program. 153(1), 133\u2013177 (2015)","journal-title":"Math. Program."},{"key":"1563_CR31","doi-asserted-by":"publisher","unstructured":"Feige, U., Jozeph, S.: Demand queries with preprocessing. In: Automata, Languages, and Programming\u201441st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8\u201311, 2014, Proceedings, Part I, pp. 477\u2013488, (2014) https:\/\/doi.org\/10.1007\/978-3-662-43948-7_40","DOI":"10.1007\/978-3-662-43948-7_40"},{"key":"1563_CR32","doi-asserted-by":"crossref","unstructured":"Fiorini, S., Massar, S., Pokutta, S., Tiwary, H.R., De Wolf, R.: Linear versus semidefinite extended formulations: exponential separation and strong lower bounds. In: Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, ACM, pp. 95\u2013106 (2012)","DOI":"10.1145\/2213977.2213988"},{"issue":"2","key":"1563_CR33","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1145\/2716307","volume":"62","author":"S Fiorini","year":"2015","unstructured":"Fiorini, S., Massar, S., Pokutta, S., Tiwary, H.R., Wolf, R.D.: Exponential lower bounds for polytopes in combinatorial optimization. J. ACM (JACM) 62(2), 17 (2015)","journal-title":"J. ACM (JACM)"},{"issue":"4","key":"1563_CR34","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1145\/4221.4225","volume":"32","author":"EC Freuder","year":"1985","unstructured":"Freuder, E.C.: A sufficient condition for backtrack-bounded search. J. ACM 32(4), 755\u2013761 (1985). https:\/\/doi.org\/10.1145\/4221.4225","journal-title":"J. ACM"},{"key":"1563_CR35","doi-asserted-by":"publisher","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"DR Fulkerson","year":"1965","unstructured":"Fulkerson, D.R., Gross, O.: Incidence matrices and interval graphs. Pac. J. Math. 15, 835\u2013855 (1965)","journal-title":"Pac. J. Math."},{"key":"1563_CR36","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.dam.2017.04.042","volume":"248","author":"J Gajarsk\u00fd","year":"2017","unstructured":"Gajarsk\u00fd, J., Hlin\u011bn\u00fd, P., Tiwary, H.R.: Parameterized extension complexity of independent set and related problems. Discret. Appl. Math. 248, 56\u201367 (2017)","journal-title":"Discret. Appl. Math."},{"key":"1563_CR37","doi-asserted-by":"crossref","unstructured":"G\u00f6\u00f6s, M., Jain, R., Watson, T.: Extension complexity of independent set polytopes. In: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, pp. 565\u2013572 (2016)","DOI":"10.1109\/FOCS.2016.67"},{"issue":"2","key":"1563_CR38","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1287\/moor.1120.0575","volume":"38","author":"J Gouveia","year":"2013","unstructured":"Gouveia, J., Parrilo, P.A., Thomas, R.R.: Lifts of convex sets and cone factorizations. Math. Oper. Res. 38(2), 248\u2013264 (2013)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"1563_CR39","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1206035.1206036","volume":"54","author":"M Grohe","year":"2007","unstructured":"Grohe, M.: The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM (JACM) 54(1), 1 (2007)","journal-title":"J. ACM (JACM)"},{"key":"1563_CR40","doi-asserted-by":"crossref","unstructured":"Guibas, L.J., Hershberger, J.E., Mitchell, J.S., Snoeyink, J.S.: Approximating polygons and subdivisions with minimum link paths. In: International Symposium on Algorithms, Springer, pp. 151\u2013162 (1991)","DOI":"10.1007\/3-540-54945-5_59"},{"issue":"1\u20132","key":"1563_CR41","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/BF01917434","volume":"8","author":"R Halin","year":"1976","unstructured":"Halin, R.: S-functions for graphs. J. Geom. 8(1\u20132), 171\u2013186 (1976)","journal-title":"J. Geom."},{"issue":"4","key":"1563_CR42","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. J. ACM 48(4), 798\u2013859 (2001). https:\/\/doi.org\/10.1145\/502090.502098","journal-title":"J. ACM"},{"issue":"4","key":"1563_CR43","doi-asserted-by":"publisher","first-page":"P4","DOI":"10.37236\/5474","volume":"22","author":"P Kolman","year":"2015","unstructured":"Kolman, P., Kouteck\u00fd, M.: Extended formulation for csp that is compact for instances of bounded treewidth. Electron. J. Combin. 22(4), P4\u201330 (2015)","journal-title":"Electron. J. Combin."},{"key":"1563_CR44","unstructured":"Kolman, P., Kouteck\u00fd, M., Tiwary, H.R.: Extension complexity, mso logic, and treewidth (2015). ArXiv preprint arXiv:1507.04907"},{"issue":"3","key":"1563_CR45","doi-asserted-by":"publisher","first-page":"822","DOI":"10.1137\/05064504X","volume":"17","author":"J Lasserre","year":"2006","unstructured":"Lasserre, J.: Convergent SDP relaxations in polynomial optimization with sparsity. SIAM J. Optim. 17(3), 822\u2013843 (2006)","journal-title":"SIAM J. Optim."},{"key":"1563_CR46","unstructured":"Laurent, M.: Sum of squares, moment matrices and optimization over polynomials. IMA, pp. 1\u2013147 (2010)"},{"key":"1563_CR47","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198522195.001.0001","volume-title":"Graphical Models","author":"SL Lauritzen","year":"1996","unstructured":"Lauritzen, S.L.: Graphical Models. Oxford University Press, Oxford (1996)"},{"key":"1563_CR48","doi-asserted-by":"crossref","unstructured":"Lee, J.R., Raghavendra, P., Steurer, D.: Lower bounds on the size of semidefinite programming relaxations. In: Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, ACM, pp. 567\u2013576 (2015)","DOI":"10.1145\/2746539.2746599"},{"key":"1563_CR49","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Known algorithms on graphs of bounded treewidth are probably optimal. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, pp 777\u2013789 (2011)","DOI":"10.1137\/1.9781611973082.61"},{"key":"1563_CR50","doi-asserted-by":"publisher","first-page":"85","DOI":"10.4086\/toc.2010.v006a005","volume":"6","author":"D Marx","year":"2010","unstructured":"Marx, D.: Can you beat treewidth? Theory Comput. 6, 85\u2013112 (2010)","journal-title":"Theory Comput."},{"key":"1563_CR51","doi-asserted-by":"publisher","unstructured":"Mu\u00f1oz, G.: Integer programming techniques for polynomial optimization. PhD thesis, Columbia University (2017). https:\/\/doi.org\/10.7916\/D82F812G","DOI":"10.7916\/D82F812G"},{"key":"1563_CR52","unstructured":"Pearl, J.: Reverend bayes on inference engines: a distributed hierarchical approach. In: Proceedings of the National Conference on Artificial Intelligence, pp. 133\u2013136 (1982)"},{"issue":"1","key":"1563_CR53","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N Robertson","year":"1984","unstructured":"Robertson, N., Seymour, P.: Graph minors III. Planar tree-width. J. Combin. Theory Ser. B 36(1), 49\u201364 (1984)","journal-title":"J. Combin. Theory Ser. B"},{"key":"1563_CR54","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.: Graph minors II: algorithmic aspects of tree-width. J. Algorithm 7, 309\u2013322 (1986)","journal-title":"J. Algorithm"},{"issue":"2","key":"1563_CR55","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1006\/jctb.1994.1073","volume":"62","author":"N Robertson","year":"1994","unstructured":"Robertson, N., Seymour, P., Thomas, R.: Quickly excluding a planar graph. J. Combin. Theory Ser. B 62(2), 323\u2013348 (1994). https:\/\/doi.org\/10.1006\/jctb.1994.1073","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1\u20132","key":"1563_CR56","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/s10107-012-0574-3","volume":"142","author":"T Rothvo\u00df","year":"2013","unstructured":"Rothvo\u00df, T.: Some 0\/1 polytopes need exponential size extended formulations. Math. Program. 142(1\u20132), 255\u2013268 (2013)","journal-title":"Math. Program."},{"issue":"6","key":"1563_CR57","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1145\/3127497","volume":"64","author":"T Rothvo\u00df","year":"2017","unstructured":"Rothvo\u00df, T.: The matching polytope has exponential extension complexity. J. ACM (JACM) 64(6), 41 (2017)","journal-title":"J. ACM (JACM)"},{"issue":"9","key":"1563_CR58","doi-asserted-by":"publisher","first-page":"1230","DOI":"10.1109\/31.34669","volume":"36","author":"R Tamassia","year":"1989","unstructured":"Tamassia, R., Tollis, I.G.: Planar grid embedding in linear time. IEEE Trans. Circuits Syst. 36(9), 1230\u20131234 (1989)","journal-title":"IEEE Trans. Circuits Syst."},{"key":"1563_CR59","doi-asserted-by":"crossref","unstructured":"Tiwary, H.R., Weltge, S., Zenklusen, R.: Extension complexities of Cartesian products involving a pyramid (2017). ArXiv preprint arXiv:1702.01959","DOI":"10.1016\/j.ipl.2017.07.011"},{"key":"1563_CR60","unstructured":"Wainwright, M.J., Jordan, M.I.: Treewidth-based conditions for exactness of the Sherali\u2013Adams and Lasserre relaxations. Tech. Rep. 671, University of California (2004)"},{"key":"1563_CR61","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/2200000001","volume":"1","author":"MJ Wainwright","year":"2008","unstructured":"Wainwright, M.J., Jordan, M.I.: Graphical models, exponential families, and variational inference. Found. Trends Mach. Learn. 1, 1\u2013305 (2008)","journal-title":"Found. Trends Mach. Learn."},{"key":"1563_CR62","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 programming relaxations for polynomial optimization problems with structured sparsity. SIAM J. Optim. 17, 218\u2013242 (2006)","journal-title":"SIAM J. Optim."},{"key":"1563_CR63","doi-asserted-by":"publisher","unstructured":"Wang, C., Liu, T., Cui, P., Xu, K.: A note on treewidth in random graphs. In: Combinatorial Optimization and Applications\u20145th International Conference, COCOA 2011, Zhangjiajie, China, August 4\u20136, 2011. Proceedings, pp. 491\u2013499 (2011). https:\/\/doi.org\/10.1007\/978-3-642-22616-8_38","DOI":"10.1007\/978-3-642-22616-8_38"},{"issue":"3","key":"1563_CR64","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1016\/0022-0000(91)90024-Y","volume":"43","author":"M Yannakakis","year":"1991","unstructured":"Yannakakis, M.: Expressing combinatorial optimization problems by linear programs. J. Comput. Syst. Sci. 43(3), 441\u2013466 (1991)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"1563_CR65","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3(1), 103\u2013128 (2007). https:\/\/doi.org\/10.4086\/toc.2007.v003a006","journal-title":"Theory Comput."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01563-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-020-01563-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01563-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,13]],"date-time":"2024-08-13T21:28:29Z","timestamp":1723584509000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-020-01563-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,15]]},"references-count":65,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["1563"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01563-5","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2020,9,15]]},"assertion":[{"value":"20 March 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 September 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 September 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}