Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2023) | last year (2022) | two years ago (2021) | Notes URL

Action:

login to update
Options:








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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for 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 23:06:39
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