Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | 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 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