Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Extension complexity
open-in-new
<h2 id="references">References</h2> <ol> <li id="fn:1"><p>Balas, Egon (2005), "Projection, lifting and extended formulation in integer and combinatorial optimization", Annals of Operations Research, 140: 125–161, doi:10.1007/s10479-005-3969-1, MR 2194735, S2CID 18252683 <a href="/wiki/Egon_Balas" target="_blank">/wiki/Egon_Balas</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Kaibel, Volker (2011), "Extended formulations in combinatorial optimization", Optima, 85: 2–7, arXiv:1104.1023 <a href="/wiki/Optima_(journal)" target="_blank">/wiki/Optima_(journal)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Conforti, Michele; Cornuéjols, Gérard; Zambelli, Giacomo (2013), "Extended formulations in combinatorial optimization", Annals of Operations Research, 204: 97–143, CiteSeerX 10.1.1.483.9715, doi:10.1007/s10479-012-1269-0, MR 3039264, S2CID 254236751 <a href="/wiki/G%C3%A9rard_Cornu%C3%A9jols" target="_blank">/wiki/G%C3%A9rard_Cornu%C3%A9jols</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Ben-Tal, Aharon; Nemirovski, Arkadi (2001), "On polyhedral approximations of the second-order cone", Mathematics of Operations Research, 26 (2): 193–205, doi:10.1287/moor.26.2.193.10561, MR 1895823 <a href="/wiki/Arkadi_Nemirovski" target="_blank">/wiki/Arkadi_Nemirovski</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Fiorini, Samuel; Rothvoß, Thomas; Tiwary, Hans Raj (2012), "Extended formulations for polygons", Discrete & Computational Geometry, 48 (3): 658–668, arXiv:1107.0371, doi:10.1007/s00454-012-9421-9, MR 2957636, S2CID 254032514 <a href="/wiki/Discrete_%26_Computational_Geometry" target="_blank">/wiki/Discrete_%26_Computational_Geometry</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Fiorini, Samuel; Rothvoß, Thomas; Tiwary, Hans Raj (2012), "Extended formulations for polygons", Discrete & Computational Geometry, 48 (3): 658–668, arXiv:1107.0371, doi:10.1007/s00454-012-9421-9, MR 2957636, S2CID 254032514 <a href="/wiki/Discrete_%26_Computational_Geometry" target="_blank">/wiki/Discrete_%26_Computational_Geometry</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Avis, David; Tiwary, Hans Raj (2015), "On the extension complexity of combinatorial polytopes", Mathematical Programming, 153 (1, Ser. B): 95–115, arXiv:1302.2340, doi:10.1007/s10107-014-0764-2, MR 3395543, S2CID 254143169 <a href="/wiki/David_Avis" target="_blank">/wiki/David_Avis</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Rothvoß, Thomas (2017), "The matching polytope has exponential extension complexity", Journal of the ACM, 64 (6): A41:1–A41:19, arXiv:1311.2369, doi:10.1145/3127497, MR 3713797, S2CID 47045361 <a href="/wiki/Journal_of_the_ACM" target="_blank">/wiki/Journal_of_the_ACM</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Aprile, Manuel; Fiorini, Samuel (July 2021), "Regular matroids have polynomial extension complexity", Mathematics of Operations Research, 47: 540–559, arXiv:1909.08539, doi:10.1287/moor.2021.1137, S2CID 202660764 <a href="/wiki/Mathematics_of_Operations_Research" target="_blank">/wiki/Mathematics_of_Operations_Research</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Briët, Jop; Dadush, Daniel; Pokutta, Sebastian (2015), "On the existence of 0/1 polytopes with high semidefinite extension complexity", Mathematical Programming, 153 (1, Ser. B): 179–199, arXiv:1305.3268, doi:10.1007/s10107-014-0785-x, MR 3395546, S2CID 254144689 <a href="https://ir.cwi.nl/pub/24053" target="_blank">https://ir.cwi.nl/pub/24053</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Lee, James R.; Raghavendra, Prasad; Steurer, David (2015), "Lower bounds on the size of semidefinite programming relaxations", in Servedio, Rocco A.; Rubinfeld, Ronitt (eds.), Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, Association for Computing Machinery, pp. 567–576, arXiv:1411.6317, doi:10.1145/2746539.2746599, ISBN 978-1-4503-3536-2, S2CID 14438019 <a href="978-1-4503-3536-2" target="_blank">978-1-4503-3536-2</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> </ol>