{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,16]],"date-time":"2025-06-16T23:28:40Z","timestamp":1750116520729,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2020,7,3]],"date-time":"2020-07-03T00:00:00Z","timestamp":1593734400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,7,3]],"date-time":"2020-07-03T00:00:00Z","timestamp":1593734400000},"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":["Math. Program."],"published-print":{"date-parts":[[2020,9]]},"DOI":"10.1007\/s10107-020-01535-9","type":"journal-article","created":{"date-parts":[[2020,7,3]],"date-time":"2020-07-03T11:04:14Z","timestamp":1593774254000},"page":"41-59","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Extended formulations from communication protocols in output-efficient time"],"prefix":"10.1007","volume":"183","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6805-6903","authenticated-orcid":false,"given":"Manuel","family":"Aprile","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuri","family":"Faenza","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,7,3]]},"reference":[{"key":"1535_CR1","unstructured":"Aprile, M.: On some problems related to 2-level polytopes. PhD thesis, \u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne (2018)"},{"key":"1535_CR2","doi-asserted-by":"crossref","unstructured":"Aprile, M., Faenza, Y.: Extended formulations from communication protocols in output-efficient time. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 43\u201356. Springer (2019)","DOI":"10.1007\/978-3-030-17953-3_4"},{"key":"1535_CR3","doi-asserted-by":"crossref","unstructured":"Aprile, M., Faenza, Y., Fiorini, S., Huynh, T., Macchia, M.: Extension complexity of stable set polytopes of bipartite graphs. In: CONF, vol. 10520, pp. 75\u201387. Springer, Cham (2017)","DOI":"10.1007\/978-3-319-68705-6_6"},{"key":"1535_CR4","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0167-5060(08)70342-X","volume":"5","author":"E Balas","year":"1979","unstructured":"Balas, E.: Disjunctive programming. Ann. Discret. Math. 5, 3\u201351 (1979)","journal-title":"Ann. Discret. Math."},{"key":"1535_CR5","doi-asserted-by":"crossref","unstructured":"Bazzi, A., Fiorini, S., Huang, S., Svensson, O.: Small extended formulation for knapsack cover inequalities from monotone circuits . In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2326\u20132341. SIAM (2017)","DOI":"10.1137\/1.9781611974782.153"},{"issue":"1","key":"1535_CR6","first-page":"147","volume":"44","author":"A Bazzi","year":"2018","unstructured":"Bazzi, A., Fiorini, S., Pokutta, S., Svensson, O.: No small linear program approximates vertex cover within a factor $$2- \\epsilon $$. Math. Oper. Res. 44(1), 147\u2013172 (2018)","journal-title":"Math. Oper. Res."},{"key":"1535_CR7","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/j.ejc.2014.02.003","volume":"40","author":"N Bousquet","year":"2014","unstructured":"Bousquet, N., Lagoutte, A., Thomass\u00e9, S.: Clique versus independent set. Eur. J. Comb. 40, 73\u201392 (2014). https:\/\/doi.org\/10.1016\/j.ejc.2014.02.003","journal-title":"Eur. J. Comb."},{"issue":"4","key":"1535_CR8","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1145\/2811255","volume":"63","author":"SO Chan","year":"2016","unstructured":"Chan, S.O., Lee, J.R., Raghavendra, P., Steurer, D.: Approximate constraint satisfaction requires large LP relaxations. J. ACM (JACM) 63(4), 34 (2016)","journal-title":"J. ACM (JACM)"},{"key":"1535_CR9","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.jctb.2015.04.007","volume":"115","author":"M Chudnovsky","year":"2015","unstructured":"Chudnovsky, M., Trotignon, N., Trunck, T., Vu\u0161skovi\u0107, K.: Coloring perfect graphs with no balanced skew-partitions. J. Comb. Theory Ser. B 115, 26\u201365 (2015)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1535_CR10","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1016\/0095-8956(75)90041-6","volume":"18","author":"V Chv\u00e1tal","year":"1975","unstructured":"Chv\u00e1tal, V.: On certain polytopes associated with graphs. J. Comb. Theory Ser. B 18, 138\u2013154 (1975)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"1535_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10288-010-0122-z","volume":"8","author":"M Conforti","year":"2010","unstructured":"Conforti, M., Cornu\u00e9jols, G., Zambelli, G.: Extended formulations in combinatorial optimization. 4OR 8(1), 1\u201348 (2010)","journal-title":"4OR"},{"issue":"1","key":"1535_CR12","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/s10107-014-0755-3","volume":"153","author":"Y Faenza","year":"2015","unstructured":"Faenza, Y., Fiorini, S., Grappe, R., Tiwary, H.R.: Extended formulations, nonnegative factorizations, and randomized communication protocols. Math. Program. 153(1), 75\u201394 (2015)","journal-title":"Math. Program."},{"key":"1535_CR13","doi-asserted-by":"crossref","unstructured":"Faenza, Y., Oriolo, G., Stauffer, G.: Separating stable sets in claw-free graphs via Padberg-Rao and compact linear programs. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1298\u20131308. Society for Industrial and Applied Mathematics (2012)","DOI":"10.1137\/1.9781611973099.102"},{"key":"1535_CR14","doi-asserted-by":"crossref","unstructured":"Faenza, Y., Oriolo, G., Stauffer, G.: Separation routine and extended formulations for the stable set problem in claw-free graphs. In: Mathematical Programming (2020)","DOI":"10.1007\/s10107-020-01502-4"},{"key":"1535_CR15","unstructured":"Fiorini, S., Huynh, T., Weltge, S.: Strengthening convex relaxations of 0\/1-sets using Boolean formulas. arXiv:1711.01358 (2017)"},{"key":"1535_CR16","doi-asserted-by":"crossref","unstructured":"Fiorini, S., Massar, S., Pokutta, S., Tiwary, H.R., De Wolf, R.: Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds. In: Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, pp. 95\u2013106. ACM (2012)","DOI":"10.1145\/2213977.2213988"},{"issue":"1","key":"1535_CR17","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1137\/16M109884X","volume":"47","author":"M G\u00f6\u00f6s","year":"2018","unstructured":"G\u00f6\u00f6s, M., Jain, R., Watson, T.: Extension complexity of independent set polytopes. SIAM J. Comput. 47(1), 241\u2013269 (2018)","journal-title":"SIAM J. Comput."},{"key":"1535_CR18","first-page":"325","volume-title":"North-Holland Mathematics Studies","author":"M Gr\u00f6tschel","year":"1984","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Polynomial algorithms for perfect graphs. In: Berge, C., Chv\u00e1tal, V. (eds.) North-Holland Mathematics Studies, vol. 88, pp. 325\u2013356. Elsevier, Amsterdam (1984)"},{"issue":"4","key":"1535_CR19","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 (JACM) 48(4), 798\u2013859 (2001)","journal-title":"J. ACM (JACM)"},{"key":"1535_CR20","first-page":"2","volume":"85","author":"V Kaibel","year":"2011","unstructured":"Kaibel, V.: Extended formulations in combinatorial optimization. OPTIMA 85, 2\u20137 (2011)","journal-title":"OPTIMA"},{"key":"1535_CR21","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574948","volume-title":"Communication Complexity","author":"E Kushilevitz","year":"1996","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1996)"},{"key":"1535_CR22","unstructured":"Lagoutte, A.: Personal communication (2018)"},{"issue":"1","key":"1535_CR23","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/j.disopt.2003.12.001","volume":"1","author":"J Lee","year":"2004","unstructured":"Lee, J., Leung, J., Margot, F.: Min-up\/min-down polytopes. Discret. Optim. 1(1), 77\u201385 (2004)","journal-title":"Discret. Optim."},{"issue":"1","key":"1535_CR24","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":"1535_CR25","unstructured":"Pashkovich, K.: Extended formulations for combinatorial polytopes. PhD thesis, Otto-von-Guericke-Universit\u00e4t Magdeburg (2012)"},{"key":"1535_CR26","first-page":"1","volume":"23628","author":"D Rajan","year":"2005","unstructured":"Rajan, D., Takriti, S.: Minimum up\/down polytopes of the unit commitment problem with start-up costs. IBM Res. Rep. RC 23628, 1\u201314 (2005)","journal-title":"IBM Res. Rep. RC"},{"key":"1535_CR27","doi-asserted-by":"crossref","unstructured":"Rao, A., Yehudayoff, A.: Communication Complexity: and Applications. Cambridge University Press (2020)","DOI":"10.1017\/9781108671644"},{"issue":"6","key":"1535_CR28","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)"},{"key":"1535_CR29","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2002","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, vol. 24. Springer, Berlin (2002)"},{"key":"1535_CR30","unstructured":"Weltge, S.: Sizes of linear descriptions in combinatorial optimization. PhD thesis, Otto-von-Guericke-Universit\u00e4t Magdeburg, Fakult\u00e4t f\u00fcr Mathematik (2015)"},{"key":"1535_CR31","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, 441\u2013466 (1991)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01535-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-020-01535-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01535-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,3]],"date-time":"2021-07-03T00:10:35Z","timestamp":1625271035000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-020-01535-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,3]]},"references-count":31,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["1535"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01535-9","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2020,7,3]]},"assertion":[{"value":"29 May 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 June 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 July 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}