Extension complexity

In convex geometry and polyhedral combinatorics, the extension complexity of a convex polytope is the smallest number of facets among convex polytopes that have as a projection. In this context, is called an extended formulation of ; it may have much higher dimension than .[1][2][3]

The extension complexity depends on the precise shape of , not just on its combinatorial structure. For instance, regular polygons with sides have extension complexity (expressed using big O notation),[4][5] but some other convex -gons have extension complexity at least proportional to .[5]

If a polytope describing the feasible solutions to a combinatorial optimization problem has low extension complexity, this could potentially be used to devise efficient algorithms for the problem, using linear programming on its extended formulation. For this reason, researchers have studied the extension complexity of the polytopes arising in this way.[6] For instance, it is known that the matching polytope has exponential extension complexity.[7] On the other hand, the independence polytope of regular matroids has polynomial extension complexity.[8]

The notion of extension complexity has also been generalized from linear programming to semidefinite programming, by considering projections of spectrahedra in place of projections of polytopes.[9][10]

References

  1. 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
  2. Kaibel, Volker (2011), "Extended formulations in combinatorial optimization", Optima, 85: 2–7, arXiv:1104.1023
  3. Conforti, Michele; Cornuéjols, Gérard; Zambelli, Giacomo (2013), "Extended formulations in combinatorial optimization", Annals of Operations Research, 204: 97–143, doi:10.1007/s10479-012-1269-0, MR 3039264
  4. 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
  5. 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
  6. 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
  7. 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
  8. Aprile, Manuel; Fiorini, Samuel (July 2021), "Regular matroids have polynomial extension complexity", Mathematics of Operations Research, arXiv:1909.08539, doi:10.1287/moor.2021.1137
  9. 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, doi:10.1007/s10107-014-0785-x, MR 3395546
  10. 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


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.