×

Upper bound on the number of vertices of polyhedra with 0,1-constraint matrices. (English) Zbl 1185.68777

Summary: We give upper bounds for the number of vertices of the polyhedron \(P (A,b) = \{ x \in \mathbb R^d : Ax \leqslant b\}\) when the \(m\times d\) constraint matrix \(A\) is subjected to certain restriction. For instance, if \(A\) is a 0/1-matrix, then there can be at most \(d\)! vertices and this bound is tight, or if the entries of \(A\) are non-negative integers so that each row sums to at most \(C\), then there can be at most \(C^d\) vertices. These bounds are consequences of a more general theorem that the number of vertices of \(P(A,b)\) is at most \(d\)!\(\bullet W/D\), where \(W\) is the volume of the convex hull of the zero vector and the row vectors of \(A\), and \(D\) is the smallest absolute value of any non-zero \(d\times d\) subdeterminant of \(A\).

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
90C05 Linear programming
Full Text: DOI

References:

[1] Barrow, D. L.; Smith, P. W., Spline notation applied to a volume problem, American Mathematical Monthly, 86, 1, 50-51 (1979) · Zbl 0411.51013
[2] Fleiner, T.; Kaibel, V.; Rote, G., Upper bounds on the maximal number of facets of 0/1-polytopes, European Journal of Combinatorics, 21, 121-130 (2000) · Zbl 0951.52007
[3] Kaibel, V.; Klee, V.; Ziegler, G. M., Graduate Texts in Mathematics, vol. 221 (2003), Springer: Springer New York · Zbl 1024.52001
[4] Marichal, J.-L., Volume formulas for the sliced unit cube and its hyperplane section (2006), Manuscript
[5] A. Wallner, Maximal number of vertices of polytopes defined by F-probabilities, in: Proc. 4th Internat. Symp. on Imprecise Probabilities and their Applications (ISIPTA 2005), pp. 388-395; A. Wallner, Maximal number of vertices of polytopes defined by F-probabilities, in: Proc. 4th Internat. Symp. on Imprecise Probabilities and their Applications (ISIPTA 2005), pp. 388-395
[6] Ziegler, G. M., Lectures on Polytopes, Graduate Texts in Mathematics, vol. 152 (1995), Springer: Springer Berlin · Zbl 0823.52002
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.