zbMATH — the first resource for mathematics

Extended formulations for polygons. (English) Zbl 1290.68122
Summary: The extension complexity of a polytope \(P\) is the smallest integer \(k\) such that \(P\) is the projection of a polytope \(Q\) with \(k\) facets. We study the extension complexity of \(n\)-gons in the plane. First, we give a new proof that the extension complexity of regular \(n\)-gons is \(O(\log n)\), a result originating from work by A. Ben-Tal and A. Nemirovski [Math. Oper. Res. 26, No. 2, 193–205 (2001; Zbl 1082.90133)]. Our proof easily generalizes to other permutahedra and simplifies proofs of recent results by M. Goemans [“Smallest compact formulation for the permutahedron” (2009), http://math.mit.edu/~goemans/PAPERS/permutahedron.pdf], and V. Kaibel and K. Pashkovich [Lect. Notes Comput. Sci. 6655, 287–300 (2011; Zbl 1341.90148)]. Second, we prove a lower bound of \(\sqrt{2n}\) on the extension complexity of generic \(n\)-gons. Finally, we prove that there exist \(n\)-gons whose vertices lie on an \(O(n)\times O(n ^2)\) integer grid with extension complexity \(\varOmega (\sqrt{n}/\sqrt{\log n})\).

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI arXiv
[1] Ajtai, M.; Komlós, J.; Szemerédi, E., An \(O(n\) log \(n)\) sorting network, 1-9, (1983), New York · Zbl 0523.68048
[2] Ben-Tal, A.; Nemirovski, A., On polyhedral approximations of the second-order cone, Math. Oper. Res., 26, 193-205, (2001) · Zbl 1082.90133
[3] Cohen, J. E.; Rothblum, U. G., Nonnegative ranks, decompositions, and factorizations of nonnegative matrices, Linear Algebra Appl., 190, 149-168, (1993) · Zbl 0784.15001
[4] Conforti, M.; Cornuéjols, G.; Zambelli, G., Extended formulations in combinatorial optimization, 4OR, 8, 1-48, (2010) · Zbl 1219.90193
[5] Conforti, M., Faenza, Y., Fiorini, S., Grappe, R., Tiwary, H.R.: Extended formulations, non-negative factorizations and randomized communication protocols. http://arxiv.org/abs/1105.4127 (2011) · Zbl 1370.68022
[6] Fiorini, S., Kaibel, V., Pashkovich, K., Theis, D.O.: Combinatorial bounds on nonnegative rank and extended formulations. Working paper (2011) · Zbl 1259.90111
[7] Goemans, M.: Smallest compact formulation for the permutahedron. http://math.mit.edu/ goemans/PAPERS/permutahedron.pdf (2009) · Zbl 1322.90048
[8] Hindry, M., Silverman, J.H.: Diophantine Geometry: An Introduction, 1st edn. Springer, Berlin (2000) · Zbl 0948.11023
[9] Hungerford, T.W.: Algebra. Graduate Texts in Mathematics. Springer, New York (1974)
[10] Kaibel, V., Extended formulations in combinatorial optimization, Optima, 85, 2-7, (2011)
[11] Kaibel, V.; Pashkovich, K., Constructing extended formulations from reflection relations, (2011) · Zbl 1341.90148
[12] Lang, S.: Algebra, Graduate Texts in Mathematics. Springer, Berlin (2002) · Zbl 0984.00001
[13] Martin, R. K., Using separation algorithms to generate mixed integer model reformulations, Oper. Res. Lett., 10, 119-128, (1991) · Zbl 0747.90071
[14] Rothvoß, T.: Some 0/1 polytopes need exponential size extended formulations. http://arxiv.org/abs/1105.0036 (2011)
[15] Stewart, I.: Galois Theory, 3rd edn. Chapman & Hall/CRC Mathematics. Chapman & Hall/CRC, Boca Raton (2004) · Zbl 1049.12001
[16] Vanderbeck, F.; Wolsey, L. A.; Jünger, M. (ed.); etal., Reformulation and decomposition of integer programs, 431-502, (2010), Berlin · Zbl 1187.90207
[17] Yannakakis, M., Expressing combinatorial optimization problems by linear programs, J. Comput. Syst. Sci., 43, 441-466, (1991) · Zbl 0748.90074
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.