Journal Article @Article Artikel in Fachzeitschrift
 Show entries of: this year (2021) | last year (2020) | two years ago (2019) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor(s)
 Author(s): Elbassioni, Khaled M. Lotker, Zvi Seidel, Raimund dblp dblp dblp Not MPG Author(s): Lotker, Zvi Seidel, Raimund
 BibTeX cite key*: Elbassioni2006e

 Title
 Title*: Upper bound on the number of vertices of polyhedra with 0, 1-constraint matrices

 Journal
 Journal Title*: Information Processing Letters Journal's URL: Download URL for the article: http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B6V0F-4K7NHSC-2-1&_cdi=5645&_user=43521&_orig=search&_coverDate=10%2F31%2F2006&_sk=998999997&view=c&wchp=dGLbVzb-zSkWA&md5=d357dd5313487f742ee6dd675ae2f3b2&ie=/sdarticle.pdf Language: English

 Publisher
 Publisher's Name: Elsevier Publisher's URL: Publisher's Address: Amsterdam, The Netherlands ISSN:

 Vol, No, pp, Date
 Volume*: 100 Number: 2 Publishing Date: October 2006 Pages*: 69 - 71 Number of VG Pages: Page Start: 69 Page End: 71 Sequence Number: DOI:

 Note: (LaTeX) 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$. URL for the Abstract: http://portal.acm.org/citation.cfm?id=1167732&dl=GUIDE&coll=GUIDE&CFID=15151515&CFTOKEN=6184618 Categories, Keywords: HyperLinks / References / URLs: Copyright Message: Personal Comments: Download Access Level: Intranet

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@ARTICLE{Elbassioni2006e,
AUTHOR = {Elbassioni, Khaled M. and Lotker, Zvi and Seidel, Raimund},
TITLE = {Upper bound on the number of vertices of polyhedra with 0, 1-constraint matrices},
JOURNAL = {Information Processing Letters},
PUBLISHER = {Elsevier},
YEAR = {2006},
NUMBER = {2},
VOLUME = {100},
PAGES = {69 -- 71},
MONTH = {October},
}