zbMATH — the first resource for mathematics

Smallest compact formulation for the permutahedron. (English) Zbl 1322.90048
Summary: In this note, we consider the permutahedron, the convex hull of all permutations of \(\{1,2\dots ,n\}\). We show how to obtain an extended formulation for this polytope from any sorting network. By using the optimal Ajtai-Komlós-Szemerédi sorting network [M. Ajtai et al., Combinatorica 3, 1–19 (1983; Zbl 0523.68048)], this extended formulation has \(\varTheta (n\log n)\) variables and inequalities. Furthermore, from basic polyhedral arguments, we show that this is best possible (up to a multiplicative constant) since any extended formulation has at least \(\varOmega (n \log n)\) inequalities. The results easily extend to the generalized permutahedron.

90C10 Integer programming
Full Text: DOI
[1] Ajtai, M; Komlós, J; Szemerédi, E, Sorting in \(C \log N\) parallel steps, Combinatorica, 3, 1-19, (1983) · Zbl 0523.68048
[2] Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms (2001) · Zbl 1047.68161
[3] Conforti, M; Cornuéjols, G; Zambelli, G, Extended formulations in combinatorial optimization, 4OR, 8, 1-48, (2010) · Zbl 1219.90193
[4] Fiorini, S., Kaibel, V., Pashkovich, K., Theis, D.O.: Combinatorial bounds on nonnegative rank and extended formulations. arxiv:1111.0444 (2012) · Zbl 1259.90111
[5] Fiorini, S., Massar, S., Pokutta, S., Tiwary, H.R., de Wolf, R.: Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds. In: Proceedings of the 44th ACM Symposium on Theory of Computing (STOC 2012) (2012) · Zbl 1286.90125
[6] Kaibel, V, Extended formulations in combinatorial optimization, Optima, 85, 2-7, (2011)
[7] Pashkovich, K.: Tight lower bounds on the sizes of symmetric extensions of permutahedra and similar results. arxiv:0912.3446 (2009)
[8] Paterson, MS, Improved sorting networks with \(O(\log N)\) depth, Algorithmica, 5, 75-92, (1990) · Zbl 0689.68066
[9] Rado, R, An inequality, J. Lond. Math. Soc., 27, 1-6, (1952) · Zbl 0047.29701
[10] Rothvoß, T.: Some \(0/1\) polytopes need exponential size extended formulations. Math. Program. (2012) · Zbl 1282.90245
[11] Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003) · Zbl 1041.90001
[12] 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.