ausblenden:
Schlagwörter:
-
Zusammenfassung:
In this note we give upper bounds for the number of vertices of the polyhedron
$P(A,b) = \{x \in Rd: Ax < 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 $Cd$ vertices. These bounds are consequences of a more
general theorem that the number of vertices of $P(A,b)$ is at most $d! ċ 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$.
