×

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.

MSC:

90C10 Integer programming

Citations:

Zbl 0523.68048
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Ajtai, M., Komlós, J., Szemerédi, E.: Sorting in \[C \log N\] ClogN 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) · Zbl 1310.90100
[8] Paterson, M.S.: Improved sorting networks with \[O(\log N)O\](logN) 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/10/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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.