TY - JOUR

T1 - Upper bound on the number of vertices of polyhedra with 0, 1-constraint matrices

AU - Elbassioni, Khaled

AU - Lotker, Zvi

AU - Seidel, Raimund

PY - 2006/10/31

Y1 - 2006/10/31

N2 - In this note we give upper bounds for the number of vertices of the polyhedron P (A, b) = {x ∈ Rd : A x ≤ b} when the m × 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 × d subdeterminant of A.

AB - In this note we give upper bounds for the number of vertices of the polyhedron P (A, b) = {x ∈ Rd : A x ≤ b} when the m × 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 × d subdeterminant of A.

KW - Computational geometry

KW - Linear programming

KW - Polyhedron

KW - Upper bounds

UR - http://www.scopus.com/inward/record.url?scp=33746926017&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2006.05.011

DO - 10.1016/j.ipl.2006.05.011

M3 - Article

AN - SCOPUS:33746926017

SN - 0020-0190

VL - 100

SP - 69

EP - 71

JO - Information Processing Letters

JF - Information Processing Letters

IS - 2

ER -