{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,8]],"date-time":"2024-08-08T19:56:35Z","timestamp":1723146995687},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,3,24]],"date-time":"2017-03-24T00:00:00Z","timestamp":1490313600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2018,2]]},"DOI":"10.1007\/s10107-017-1134-7","type":"journal-article","created":{"date-parts":[[2017,3,24]],"date-time":"2017-03-24T06:28:47Z","timestamp":1490336927000},"page":"381-394","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Maximum semidefinite and linear extension complexity of families of polytopes"],"prefix":"10.1007","volume":"167","author":[{"given":"Gennadiy","family":"Averkov","sequence":"first","affiliation":[]},{"given":"Volker","family":"Kaibel","sequence":"additional","affiliation":[]},{"given":"Stefan","family":"Weltge","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,3,24]]},"reference":[{"issue":"1","key":"1134_CR1","doi-asserted-by":"crossref","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 (2015)","journal-title":"Math. Program."},{"key":"1134_CR2","first-page":"3","volume-title":"Discrete Optimization II, Annals of Discrete Mathematics","author":"E Balas","year":"1979","unstructured":"Balas, E.: Disjunctive programming. In: Hammer, P., Johnson, E., Korte, B. (eds.) Discrete Optimization II, Annals of Discrete Mathematics, vol. 5, pp. 3\u201351. Elsevier, Amsterdam (1979)"},{"key":"1134_CR3","volume-title":"A Course in Convexity, Graduate Studies in Mathematics","author":"A Barvinok","year":"2002","unstructured":"Barvinok, A.: A Course in Convexity, Graduate Studies in Mathematics, vol. 54. American Mathematical Society, Providence (2002)"},{"issue":"1","key":"1134_CR4","doi-asserted-by":"crossref","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","key":"1134_CR5","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/s10479-012-1269-0","volume":"204","author":"M Conforti","year":"2013","unstructured":"Conforti, M., Cornu\u00e9jols, G., Zambelli, G.: Extended formulations in combinatorial optimization. Ann. Oper. Res. 204(1), 97\u2013143 (2013)","journal-title":"Ann. Oper. Res."},{"issue":"1, Ser. B","key":"1134_CR6","doi-asserted-by":"crossref","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, Ser. B), 133\u2013177 (2015)","journal-title":"Math. Program."},{"key":"1134_CR7","doi-asserted-by":"crossref","unstructured":"Fiorini, S., Massar, S., Pokutta, S., Tiwary, H.R., de\u00a0Wolf, R.: Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds. In: Proceedings of the 44th ACM Symposium on Theory of Computing (STOC 2012), pp. 95\u2013106. ACM, New-York (NY), USA (2012)","DOI":"10.1145\/2213977.2213988"},{"issue":"3","key":"1134_CR8","doi-asserted-by":"crossref","first-page":"658","DOI":"10.1007\/s00454-012-9421-9","volume":"48","author":"S Fiorini","year":"2012","unstructured":"Fiorini, S., Rothvo\u00df, T., Tiwary, H.R.: Extended formulations for polygons. Discret. comput. geom. 48(3), 658\u2013668 (2012)","journal-title":"Discret. comput. geom."},{"issue":"1","key":"1134_CR9","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/s10107-014-0757-1","volume":"153","author":"MX Goemans","year":"2014","unstructured":"Goemans, M.X.: Smallest compact formulation for the permutahedron. Math. Program. 153(1), 5\u201311 (2014)","journal-title":"Math. Program."},{"issue":"2","key":"1134_CR10","doi-asserted-by":"crossref","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, Ser. A","key":"1134_CR11","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/s10107-008-0240-y","volume":"122","author":"JW Helton","year":"2010","unstructured":"Helton, J.W., Nie, J.: Semidefinite representation of convex sets. Math. Program. 122(1, Ser. A), 21\u201364 (2010)","journal-title":"Math. Program."},{"key":"1134_CR12","doi-asserted-by":"crossref","unstructured":"Helton, J.W., Nie, J.: Semidefinite representation of convex sets and convex hulls. In: Handbook on Semidefinite, Conic and Polynomial Optimization, Internat. Ser. Oper. Res. Management Sci., vol. 166, pp. 77\u2013112. Springer, New York (2012)","DOI":"10.1007\/978-1-4614-0769-0_4"},{"issue":"5","key":"1134_CR13","doi-asserted-by":"crossref","first-page":"654","DOI":"10.1002\/cpa.20155","volume":"60","author":"JW Helton","year":"2007","unstructured":"Helton, J.W., Vinnikov, V.: Linear matrix inequality representation of sets. Commun. Pure Appl. Math. 60(5), 654\u2013674 (2007)","journal-title":"Commun. Pure Appl. Math."},{"key":"1134_CR14","unstructured":"Kaibel, V.: Extended formulations in combinatorial optimization. Optima 85 (2011). http:\/\/www.mathopt.org\/Optima-Issues\/optima85.pdf"},{"issue":"2","key":"1134_CR15","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1007\/s00454-014-9655-9","volume":"53","author":"V Kaibel","year":"2015","unstructured":"Kaibel, V., Weltge, S.: A short proof that the extension complexity of the correlation polytope grows exponentially. Discret. Comput. Geom. 53(2), 396\u2013401 (2015)","journal-title":"Discret. Comput. Geom."},{"key":"1134_CR16","doi-asserted-by":"crossref","unstructured":"Kramer, M.R., van Leeuwen, J.: The VLSI complexity of Boolean functions. In: Logic and Machines: Decision Problems and Complexity, pp. 397\u2013407. Springer (1984)","DOI":"10.1007\/3-540-13331-3_55"},{"key":"1134_CR17","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 47th ACM Symposium on Theory of Computing (STOC 2015), pp. 567\u2013576. ACM, New-York (NY), USA (2015)","DOI":"10.1145\/2746539.2746599"},{"key":"1134_CR18","doi-asserted-by":"crossref","unstructured":"Padrol, A.: Extension complexity of polytopes with few vertices or facets. arXiv:1602.06894 (2016)","DOI":"10.1016\/j.jcta.2016.04.001"},{"issue":"4","key":"1134_CR19","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1016\/j.orl.2013.03.010","volume":"41","author":"S Pokutta","year":"2013","unstructured":"Pokutta, S., Van Vyve, M.: A note on the extension complexity of the knapsack polytope. Oper. Res. Lett. 41(4), 347\u2013350 (2013)","journal-title":"Oper. Res. Lett."},{"key":"1134_CR20","volume-title":"Convex analysis. Princeton Landmarks in Mathematics","author":"RT Rockafellar","year":"1997","unstructured":"Rockafellar, R.T.: Convex analysis. Princeton Landmarks in Mathematics. Princeton University Press, Princeton (1997)"},{"issue":"1\u20132","key":"1134_CR21","doi-asserted-by":"crossref","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."},{"key":"1134_CR22","doi-asserted-by":"crossref","unstructured":"Rothvo\u00df, T.: The matching polytope has exponential extension complexity. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC 2014), pp. 263\u2013272. ACM, New York (NY), USA (2014)","DOI":"10.1145\/2591796.2591834"},{"issue":"5","key":"1134_CR23","doi-asserted-by":"crossref","first-page":"2606","DOI":"10.1016\/j.aim.2011.07.014","volume":"228","author":"C Scheiderer","year":"2011","unstructured":"Scheiderer, C.: Convex hulls of curves of genus one. Adv. Math. 228(5), 2606\u20132622 (2011)","journal-title":"Adv. Math."},{"issue":"1","key":"1134_CR24","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/j.1538-7305.1949.tb03624.x","volume":"28","author":"CE Shannon","year":"1949","unstructured":"Shannon, C.E.: The synthesis of two-terminal switching circuits. Bell Syst. Tech. J. 28(1), 59\u201398 (1949)","journal-title":"Bell Syst. Tech. J."},{"key":"1134_CR25","unstructured":"Shitov, Y.: Sublinear extensions of polygons. arXiv:1412.0728 (2014)"},{"issue":"3","key":"1134_CR26","doi-asserted-by":"crossref","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."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-017-1134-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-017-1134-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-017-1134-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,20]],"date-time":"2019-09-20T00:37:34Z","timestamp":1568939854000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-017-1134-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,24]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,2]]}},"alternative-id":["1134"],"URL":"https:\/\/doi.org\/10.1007\/s10107-017-1134-7","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,3,24]]}}}