{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T07:43:21Z","timestamp":1648539801756},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2016,3,25]],"date-time":"2016-03-25T00:00:00Z","timestamp":1458864000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"NSF","award":["CMMI-1300144"],"award-info":[{"award-number":["CMMI-1300144"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2016,11]]},"DOI":"10.1007\/s10107-016-0989-3","type":"journal-article","created":{"date-parts":[[2016,3,25]],"date-time":"2016-03-25T09:11:59Z","timestamp":1458897119000},"page":"407-431","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Average case polyhedral complexity of the maximum stable set problem"],"prefix":"10.1007","volume":"160","author":[{"given":"G\u00e1bor","family":"Braun","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Samuel","family":"Fiorini","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":[[2016,3,25]]},"reference":[{"key":"989_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. Progr. B 153, 95\u2013115 (2015)","journal-title":"Math. Progr. B"},{"key":"989_CR2","doi-asserted-by":"crossref","unstructured":"Bazzi, A., Fiorini, S., Pokutta, S., Svensson, O.: Small linear programs cannot approximate Vertex Cover within a factor of $$2 - \\varepsilon $$ 2 - \u03b5 . In: IEEE 56th Annual symposium on foundations of computer science (FOCS), pp. 1123\u20131142 (2015)","DOI":"10.1109\/FOCS.2015.73"},{"key":"989_CR3","doi-asserted-by":"crossref","unstructured":"Braun, G., Pokutta, S.: Common information and unique disjointness. In: IEEE 54th Annual symposium on foundations of computer science (FOCS), pp. 688\u2013697 (2013)","DOI":"10.1109\/FOCS.2013.79"},{"key":"989_CR4","doi-asserted-by":"crossref","unstructured":"Braun, G., Pokutta, S.: The matching polytope does not admit fully-polynomial size relaxation schemes. In: Proceedings of the 26th annual ACM-SIAM symposium on discrete algorithms (SODA), pp. 837\u2013846 (2015)","DOI":"10.1137\/1.9781611973730.57"},{"key":"989_CR5","doi-asserted-by":"crossref","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, 756\u2013772 (2015a)","journal-title":"Math. Oper. Res."},{"key":"989_CR6","doi-asserted-by":"crossref","unstructured":"Braun, G., Pokutta, S., Zink, D.: Inapproximability of combinatorial problems via small LPs and SDPs. In: Proceedings of the 47th annual ACM symposium on theory of computing (STOC), pp. 107\u2013116 (2015b)","DOI":"10.1145\/2746539.2746550"},{"key":"989_CR7","doi-asserted-by":"crossref","unstructured":"Braverman, M., Moitra, A.: An information complexity approach to extended formulations. In: Proceedings of the 45th annual ACM symposium on theory of computing (STOC), pp. 161\u2013170 (2013)","DOI":"10.1145\/2488608.2488629"},{"key":"989_CR8","doi-asserted-by":"crossref","unstructured":"Chan, S., Lee, J., Raghavendra, P., Steurer, D.: Approximate constraint satisfaction requires large LP relaxations. In: IEEE 54th annual symposium on foundations of computer science (FOCS 2013), pp. 350\u2013359 (2013)","DOI":"10.1109\/FOCS.2013.45"},{"key":"989_CR9","doi-asserted-by":"crossref","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\u201348 (2010)","journal-title":"4OR"},{"key":"989_CR10","volume-title":"Graph Theory","author":"R Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory. Springer, Heidelberg (2005)"},{"key":"989_CR11","doi-asserted-by":"crossref","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"69B","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Maximum matching and a polyhedron with 0, 1 vertices. J. Res. Natl. Bur. Stand. 69B, 125\u2013130 (1965)","journal-title":"J. Res. Natl. Bur. Stand."},{"key":"989_CR12","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 44th annual ACM symposium on theory of computing (STOC) (2012)","DOI":"10.1145\/2213977.2213988"},{"issue":"2","key":"989_CR13","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1145\/2716307","volume":"62","author":"S Fiorini","year":"2015","unstructured":"Fiorini, S., Massar, S., Pokutta, S., Tiwary, H., Wolf, Rd: Exponential lower bounds for polytopes in combinatorial optimization. J. ACM 62(2), 17 (2015)","journal-title":"J. ACM"},{"key":"989_CR14","doi-asserted-by":"crossref","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, 1115\u20131145 (1995)","journal-title":"J. ACM"},{"key":"989_CR15","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":"989_CR16","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1007\/s00454-014-9655-9","volume":"53","author":"V Kaibel","year":"2014","unstructured":"Kaibel, V., Weltge, S.: A short proof that the extension complexity of the correlation polytope grows exponentially. Discrete Comput. Geom. 53, 397\u2013401 (2014)","journal-title":"Discrete Comput. Geom."},{"key":"989_CR17","doi-asserted-by":"crossref","unstructured":"Lee, J., Raghavendra, P., Steurer, D.: Lower bounds on the size of semidefinite programming relaxations. In: Proceedings of the 47th annual ACM symposium on theory of computing (STOC), pp. 567\u2013576 (2015)","DOI":"10.1145\/2746539.2746599"},{"key":"989_CR18","unstructured":"Pashkovich, K.: Extended Formulations for Combinatorial Polytopes. PhD thesis, Magdeburg Universit\u00e4t (2012)"},{"key":"989_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, 347\u2013350 (2013)","journal-title":"Oper. Res. Lett."},{"key":"989_CR20","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/0304-3975(92)90260-M","volume":"106","author":"AA Razborov","year":"1992","unstructured":"Razborov, A.A.: On the distributional complexity of disjointness. Theor. Comput. Sci. 106, 385\u2013390 (1992)","journal-title":"Theor. Comput. Sci."},{"key":"989_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. Progr. A 142, 255\u2013268 (2013)","journal-title":"Math. Progr. A"},{"key":"989_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), pp. 263\u2013272 (2014)","DOI":"10.1145\/2591796.2591834"},{"key":"989_CR23","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1002\/net.10010","volume":"39","author":"J Williams","year":"2002","unstructured":"Williams, J.: A linear-size zero-one programming model for the minimum spanning tree problem in planar graphs. Networks 39, 53\u201360 (2002)","journal-title":"Networks"},{"issue":"3","key":"989_CR24","doi-asserted-by":"crossref","first-page":"681","DOI":"10.1137\/S0097539702407345","volume":"32","author":"Rd Wolf","year":"2003","unstructured":"Wolf, Rd: Nondeterministic quantum query and communication complexities. SIAM J. Comput. 32(3), 681\u2013699 (2003)","journal-title":"SIAM J. Comput."},{"key":"989_CR25","doi-asserted-by":"crossref","unstructured":"Yannakakis, M.: Expressing combinatorial optimization problems by linear programs (extended abstract). In: Proceedings of the 20th annual ACM symposium on theory of computing (STOC), pp. 223\u2013228 (1988)","DOI":"10.1145\/62212.62232"},{"key":"989_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, 441\u2013466 (1991)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-016-0989-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-016-0989-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-016-0989-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-016-0989-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,5]],"date-time":"2019-09-05T20:08:31Z","timestamp":1567714111000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-016-0989-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,3,25]]},"references-count":26,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2016,11]]}},"alternative-id":["989"],"URL":"https:\/\/doi.org\/10.1007\/s10107-016-0989-3","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,3,25]]}}}