**ID:**14357 |

**Type of Publication:** Journal Articles |

**Authors:** Khaled.Elbassioni, Zvi Lotker, Raimund.Seidel |

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

**Name of the Journal:** Information Processing Letters |

**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 is a member of the set of R^{d} : A x [less-than or equal to] 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 ! s 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. © 2006 Elsevier B.V. All rights reserved. |

**Keywords:** Constraint theory;Computational geometry;Integer programming;Number theory;Linear programming; , |

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