## DIMACS TR: 2005-30

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

### Authors: Khaled Elbassioni, Zvi Lotker and Raimund Seidel

**
ABSTRACT
**

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

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2005/2005-30.ps.gz

DIMACS Home Page