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

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