**ID:**14358 |

**Type of Publication:** Journal Articles |

**Authors:** Zvi Lotker, K.Elbassioni, R.Seidel |

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

**Name of the Journal:** Inf. Process. Lett. (Netherlands) |

**Year:** 2006 |

**Volume:** 100 |

**Issue:** 2 |

**Pages:** 69 - 71 |

**Abstract:** In this note we give upper bounds for the number of vertices of the polyhedron P(A,b)={x∈ℝ^{d}: Ax⩽b} when the m×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 C^{d} 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×d subdeterminant of *A*. [All rights reserved Elsevier] |

**Keywords:** computational geometry;matrix algebra;vectors; , |

**Last Updated:** 9/4/2007 12:00:00 AM |