Regular Matroids Have Polynomial Extension Complexity

References

• [1] Aprile M, Cevallos A, Faenza Y (2018) On 2-level polytopes arising in combinatorial settings. SIAM J. Discrete Math. 32(3):1857–1886.Crossref, Google Scholar
• [2] Balas E (1979) Disjunctive programming. Ann. Discrete Math. 5:3–51.Crossref, Google Scholar
• [3] Conforti M, Cornuéjols G, Zambelli G (2010) Extended formulations in combinatorial optimization. 4OR 8(1):1–48.Crossref, Google Scholar
• [4] Conforti M, Fiorini S, Pashkovich K (2016) Cut dominants and forbidden minors. SIAM J. Discrete Math. 30(3):1571–1589.Crossref, Google Scholar
• [5] Conforti M, Rinaldi G, Wolsey L (2004) On the cut polyhedron. Discrete Math. 277(1–3):279–285.Crossref, Google Scholar
• [6] Conforti M, Kaibel V, Walter M, Weltge S (2015) Subgraph polytopes and independence polytopes of count matroids. Oper. Res. Lett. 43(5):457–460.Crossref, Google Scholar
• [7] Dinitz M, Kortsarz G (2014) Matroid secretary for regular and decomposable matroids. SIAM J. Comput. 43(5):1807–1830.Crossref, Google Scholar
• [8] Fiorini S, Massar S, Pokutta S, Tiwary HR, De Wolf R (2012) Linear vs. semidefinite extended formulations: Exponential separation and strong lower bounds. Howard K, Toniann P, eds. Proc. 44th Annual ACM Symp. Theory Comput. (Association for Computing Machinery, New York), 95–106.Google Scholar
• [9] Huynh T (2016) Extended formulations and matroid polytopes. The Matroid Union (February 13), http://matroidunion.org/?p=1603.Google Scholar
• [10] Göös M, Jain R, Watson T (2018) Extension complexity of independent set polytopes. SIAM J. Comput. 47(1):241–269.Crossref, Google Scholar
• [11] Gurjar R, Vishnoi NK (2017) Extended formulations for polytopes of regular matroids. Preprint, submitted December 31, https://arxiv.org/abs/1701.00538.Google Scholar
• [12] Iwata S, Kamiyama N, Katoh N, Kijima S, Okamoto Y (2016) Extended formulations for sparsity matroids. Math. Programming 158(1–2):565–574.Crossref, Google Scholar
• [13] Kaibel V, Pashkovich K, Theis DO (2012) Symmetry matters for sizes of extended formulations. SIAM J. Discrete Math. 26(3):1361–1382.Crossref, Google Scholar
• [14] Kaibel V, Lee J, Walter M, Weltge S (2016) Extended formulations for independence polytopes of regular matroids. Graphs Combinatorics 32(5):1931–1944.Crossref, Google Scholar
• [15] Kaibel V, Lee J, Walter M, Weltge S (2020) Correction to: Extended formulations for independence polytopes of regular matroids. Graphs Combinatorics 36(1):177–179.Crossref, Google Scholar
• [16] KapadiaR (2014) Finding shortest circuits in binary matroids. Blog, Matroid Union (November 30), http://matroidunion.org/?p=1106.Google Scholar
• [17] Martin RK (1991) Using separation algorithms to generate mixed integer model reformulations. Oper. Res. Lett. 10(3):119–128.Crossref, Google Scholar
• [18] OxleyJG (2006) Matroid Theory, vol 3 (Oxford University Press, UK).Google Scholar
• [19] Rothvoß T (2013) Some 0/1 polytopes need exponential size extended formulations. Math. Programming 142(1–2):255–268.Crossref, Google Scholar
• [20] Rothvoß T (2014) The matching polytope has exponential extension complexity. David S, ed. Proc. 46th Annual ACM Symp. Theory Comput. (Association for Computing Machinery, New York), 263–272.Google Scholar
• [21] Schrijver A (1998) Theory of Linear and Integer Programming (John Wiley & Sons, NJ).Google Scholar
• [22] Schrijver A (2003) Combinatorial Optimization: Polyhedra and Efficiency, vol. 24 (Springer Science & Business Media, Berlin, Germany).Google Scholar
• [23] Seymour PD (1980) Decomposition of regular matroids. J. Combin. Theory Ser. B 28(3):305–359.Crossref, Google Scholar
• [24] Tamir A (1994) Polynomial formulations of min-cut problems. Working paper, Department of Statistic and Operations Research, Tel Aviv University, Israel.Google Scholar
• [25] Truemper K (1992) Matroid Decomposition, vol. 6 (Academic Press, Boston).Google Scholar
• [26] Vardy A (1997) The intractability of computing the minimum distance of a code. IEEE Trans. Inform. Theory 43(6):1757–1766.Crossref, Google Scholar
• [27] Weltge S (2015) Sizes of linear descriptions in combinatorial optimization. Unpublished PhD thesis, Otto-von-Guericke-Universität Magdeburg, Fakultät für Mathematik.Google Scholar
• [28] Williams J (2002) A linear-size zero-one programming model for the minimum spanning tree problem in planar graphs. Networks 39(1):53–60.Crossref, Google Scholar
• [29] Wong RT (1980) Integer programming formulations of the traveling salesman problem. Jacob R, ed. Proc. IEEE Internat. Conf. Circuits Comput. (IEEE Press, Piscataway, NJ), 149–152.Google Scholar
• [30] Yannakakis M (1991) Expressing combinatorial optimization problems by linear programs. J. Comput. System Sci. 43(3):441–466.Crossref, Google Scholar