Journal Article
@Article
Artikel in Fachzeitschrift
Show entries of:
this year
(2022) |
last year
(2021) |
two years ago
(2020) |
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, Abstract, ©
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},
ADDRESS = {Amsterdam, The Netherlands},
MONTH = {October},
}
Entry last modified by Christine Kiesel, 05/02/2007
Edit History (please click the blue arrow to see the details)
Edit History (please click the blue arrow to see the details)
Editor(s)
Khaled Elbassioni
Created
12/27/2006 11:06:39 PM
Revisions
5.
4.
3.
2.
1.
Editor(s)
Christine Kiesel
Khaled Elbassioni
Khaled Elbassioni
Khaled Elbassioni
Khaled Elbassioni
Edit Dates
02.05.2007 15:29:46
03/06/2007 05:21:54 PM
03/06/2007 05:21:21 PM
03/06/2007 05:20:20 PM
07.02.2007 16:29:56