Upper Bound on the Number of Vertices of Polyhedra with $0,1$-Constraint Matrices

Khaled Elbassioni, Zvi Lotker, Raimund Seidel

In this note we show that the maximum number of vertices in any polyhedron $P=\{x\in {\mathbb{R}}^d:Ax\le b\}$ with $0,1$-constraint matrix $A$ and a real vector $b$ is at most $d…