English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Upper bound on the number of vertices of polyhedra with 0, 1-constraint matrices

Elbassioni, K., Lotker, Z., & Seidel, R. (2006). Upper bound on the number of vertices of polyhedra with 0, 1-constraint matrices. Information Processing Letters, 100, 69-71.

Item is

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Elbassioni, Khaled1, Author           
Lotker, Zvi1, Author           
Seidel, Raimund, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: In this note we give upper bounds for the number of vertices of the polyhedron $P(A,b) = \{x \in Rd: Ax < b\}$ when the $m \times 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 \times d$ subdeterminant of $A$.

Details

show
hide
Language(s): eng - English
 Dates: 2007-03-062006
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: Peer
 Identifiers: eDoc: 314648
Other: Local-ID: C1256428004B93B8-661374BD9200F9CAC125725100797570-Elbassioni2006e
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Information Processing Letters
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 100 Sequence Number: - Start / End Page: 69 - 71 Identifier: -