✦ LIBER ✦

On the Number of Faces of Certain Transportation Polytopes

✍ Scribed by Igor Pak

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 93 KB
Volume: 21
Category: Article
ISSN: 0195-6698
DOI: 10.1006/eujc.1999.0392

No coin nor oath required. For personal study only.

✦ Synopsis

Define the transportation polytope T n,m to be a polytope of non-negative n × m matrices with row sums equal to m and column sums equal to n. We present a new recurrence relation for the numbers f k of the k-dimensional faces for the transportation polytope T n,n+1 . This gives an efficient algorithm for computing the numbers f k , which solves the problem known to be computationally hard in a general case.

📜 SIMILAR VOLUMES

Polytopal Approximation Bounding the Num

Polytopal Approximation Bounding the Number of k-Faces

✍ Károly Böröczky Jr. 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 246 KB

The number of faces of a simplicial conv

The number of faces of a simplicial convex polytope

✍ Richard P Stanley 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 177 KB

On the Number of Lattice Free Polytopes

✍ Imre Bárány; Jean-Michel Kantor 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 110 KB

asked for estimates for the number of equivalence classes of lattice polytopes, under the group of unimodular affine transformations. What we investigate here is the analogous question for lattice free polytopes. Some of the results: the number of equivalence classes of lattice free simplices of vol

Upper Bounds on the Maximal Number of Fa

Upper Bounds on the Maximal Number of Facets of 0/1-Polytopes

✍ Tamás Fleiner; Volker Kaibel; Günter Rote 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 157 KB

We prove two new upper bounds on the number of facets that a d-dimensional 0/1-polytope can have. The first one is 2(d -1)!+2(d -1) (which is the best one currently known for small dimensions), while the second one of O((d -2)!) is the best known bound for large dimensions.

On Certain Algebras of Reduction Number

On Certain Algebras of Reduction Number One

✍ Margherita Barile; Marcel Morales 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 188 KB

Linear Conditions on the Number of Faces

Linear Conditions on the Number of Faces of Manifolds with Boundary

✍ Beifang Chen; Min Yan 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 284 KB

The Euler equation and the Dehn᎐Sommerville equations are known to be the Ž . Ž only rational linear conditions for f-vectors number of simplices at various . dimensions of triangulations of spheres. We generalize this fact to arbitrary triangulations, linear triangulations of manifolds, and polytop