{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T19:43:33Z","timestamp":1778615013045,"version":"3.51.4"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2017,9,28]],"date-time":"2017-09-28T00:00:00Z","timestamp":1506556800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["1115849"],"award-info":[{"award-number":["1115849"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"ONR","award":["N00014-11-1-0053"],"award-info":[{"award-number":["N00014-11-1-0053"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2017,12,31]]},"abstract":"<jats:p>\n            A popular method in combinatorial optimization is to express polytopes\n            <jats:italic>P<\/jats:italic>\n            , which may potentially have exponentially many facets, as solutions of linear programs that use few extra variables to reduce the number of constraints down to a polynomial. After two decades of standstill, recent years have brought amazing progress in showing lower bounds for the so-called\n            <jats:italic>extension complexity<\/jats:italic>\n            , which for a polytope\n            <jats:italic>P<\/jats:italic>\n            denotes the smallest number of inequalities necessary to describe a higher-dimensional polytope\n            <jats:italic>Q<\/jats:italic>\n            that can be linearly projected on\n            <jats:italic>P<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            However, the central question in this field remained wide open: can the\n            <jats:italic>perfect matching polytope<\/jats:italic>\n            be written as an LP with polynomially many constraints?\n          <\/jats:p>\n          <jats:p>\n            We answer this question negatively. In fact, the extension complexity of the perfect matching polytope in a complete\n            <jats:italic>n<\/jats:italic>\n            -node graph is 2\n            <jats:sup>\n              \u03a9 (\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            . By a known reduction, this also improves the lower bound on the extension complexity for the TSP polytope from 2\n            <jats:sup>\n              \u03a9 (\u221a\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            to 2\n            <jats:sup>\n              \u03a9 (\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            .\n          <\/jats:p>","DOI":"10.1145\/3127497","type":"journal-article","created":{"date-parts":[[2017,9,29]],"date-time":"2017-09-29T12:44:38Z","timestamp":1506689078000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":63,"title":["The Matching Polytope has Exponential Extension Complexity"],"prefix":"10.1145","volume":"64","author":[{"given":"Thomas","family":"Rothvoss","sequence":"first","affiliation":[{"name":"University of Washington, Padelford, Seattle, WA"}]}],"member":"320","published-online":{"date-parts":[[2017,9,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_6"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/0606047"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580600"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.10"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.79"},{"key":"e_1_2_1_6_1","unstructured":"G. Braun and S. Pokutta. 2014. The matching polytope does not admit fully-polynomial size relaxation schemes. CoRR abs\/1403.6710 (2014). Retrieved from http:\/\/arxiv.org\/abs\/1403.6710  G. Braun and S. Pokutta. 2014. The matching polytope does not admit fully-polynomial size relaxation schemes. CoRR abs\/1403.6710 (2014). Retrieved from http:\/\/arxiv.org\/abs\/1403.6710"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488629"},{"key":"e_1_2_1_8_1","volume-title":"European Symposium on Algorithms. 217--228","author":"Bri\u00ebt J","unstructured":"J Bri\u00ebt , D. Dadush , and S. Pokutta . 2013. On the existence of 0\/1 polytopes with high semidefinite extension complexity . In European Symposium on Algorithms. 217--228 . J Bri\u00ebt, D. Dadush, and S. Pokutta. 2013. On the existence of 0\/1 polytopes with high semidefinite extension complexity. In European Symposium on Algorithms. 217--228."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.45"},{"key":"e_1_2_1_10_1","volume-title":"Maximum matching and a polyhedron with 0,1-vertices. J. Res. Nat. Bur. Standards Sect. B 69B","author":"Edmonds J.","year":"1965","unstructured":"J. Edmonds . 1965. Maximum matching and a polyhedron with 0,1-vertices. J. Res. Nat. Bur. Standards Sect. B 69B ( 1965 ), 125--130. 0160-1741 J. Edmonds. 1965. Maximum matching and a polyhedron with 0,1-vertices. J. Res. Nat. Bur. Standards Sect. B 69B (1965), 125--130. 0160-1741"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584082"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32147-4_13"},{"key":"e_1_2_1_13_1","unstructured":"S. Fiorini. 2013. Personal communication.  S. Fiorini. 2013. Personal communication."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2012.09.015"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213988"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-012-9421-9"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(91)90038-Q"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0757-1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13036-6_11"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746599"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(91)90028-N"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.7.1.67"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2013.03.010"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0032036"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-012-0574-3"},{"key":"e_1_2_1_27_1","volume-title":"Combinatorial Optimization. Polyhedra and Efficiency","author":"Schrijver A.","unstructured":"A. Schrijver . 2003. Combinatorial Optimization. Polyhedra and Efficiency . Vol. A,B,C. Algorithms and Combinatorics, Vol. 24 . Springer-Verlag , Berlin . A. Schrijver. 2003. Combinatorial Optimization. Polyhedra and Efficiency. Vol. A,B,C. Algorithms and Combinatorics, Vol. 24. Springer-Verlag, Berlin."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(03)00052-X"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90024-Y"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3127497","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3127497","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3127497","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:29Z","timestamp":1750217429000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3127497"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,28]]},"references-count":29,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2017,12,31]]}},"alternative-id":["10.1145\/3127497"],"URL":"https:\/\/doi.org\/10.1145\/3127497","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,9,28]]},"assertion":[{"value":"2014-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-09-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}