ID:14358
Type of Publication: Journal Articles
Authors: Zvi Lotker, K.Elbassioni, R.Seidel
Title: Upper bound on the number of vertices of polyhedra with 0,1-constraint matrices
Name of the Journal: Inf. Process. Lett. (Netherlands)
Year: 2006
Volume: 100
Issue: 2
Pages: 69 - 71
Abstract: In this note we give upper bounds for the number of vertices of the polyhedron P(A,b)={x∈ℝd: Ax⩽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. [All rights reserved Elsevier]
Keywords: computational geometry;matrix algebra;vectors; ,
Last Updated: 9/4/2007 12:00:00 AM
Powered by Rami Palombo © 2005
Search in: Google Scholar  |  Scitation