On the number of faces of certain transportation polytopes

DOI10.1006/EUJC.1999.0392MaRDI QIDQ1580679zbMATH OpenOpenAlexFDO

Authors Igor Pak

Publication date 8 July 2001

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/76587ed7d35c00cb4ed2f343787131f86fa6e9df

zbMATH Keywords

algorithmnumber of facestransportation polytope

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Review text

Consider a transportation polytope \(T_{n,m}(a,b)\) i.e., the set of non-negative \(n\times m\) matrices with row sums equal to \(m\) and column sums equal to \(n\), where \(a=(a_1, \dots, a_m)\), \(b=(b_1, \dots, b_m)\) are two non-negative integer vectors, such that \(a_1+ \cdots +a_m =b_1+ \cdots +b_n\). In this paper the author presents an efficient algorithm for computing the number of faces of transportation polytopes in a special case when \(n=m+1\), \(a= (m+1, \dots,m+1)\) and \(b=(m,\dots,m)\).

Recommendations

• scientific article; zbMATH DE number 3883948
• On transportation polytopes with the minimum number of k-faces
• scientific article; zbMATH DE number 3949176
• scientific article; zbMATH DE number 3861931
• Publication:5749146
• scientific article; zbMATH DE number 3614495
• Faces of dual transportation polyhedra
• scientific article; zbMATH DE number 3916323
• Multi-index planar transportation polytopes with maximum number of vertices
• scientific article; zbMATH DE number 3904323

Cites work

• A simple way to tell a simple polytope from its graph
• Combinatorics and commutative algebra.
• Four questions on Birkhoff polytopes
• scientific article; zbMATH DE number 3828715 (Why is no real title available?)
• scientific article; zbMATH DE number 575960 (Why is no real title available?)
• scientific article; zbMATH DE number 609997 (Why is no real title available?)
• scientific article; zbMATH DE number 795108 (Why is no real title available?)
• scientific article; zbMATH DE number 848091 (Why is no real title available?)
• scientific article; zbMATH DE number 3294139 (Why is no real title available?)
• Lectures on Polytopes
• Maximal minors and their leading terms
• Permutations, matrices, and generalized Young tableaux
• Sampling contingency tables

Cited in

(12)

• Tropical determinant on transportation polytopes
• Perturbation of transportation polytopes
• Orthogonal bases for transportation polytopes applied to Latin squares, magic squares and sudoku boards
• On the closest point to the origin in transportation polytopes
• scientific article; zbMATH DE number 3861931 (Why is no real title available?)
• Random walks on the vertices of transportation polytopes with constant number of sources
• scientific article; zbMATH DE number 3916323 (Why is no real title available?)
• scientific article; zbMATH DE number 3614495 (Why is no real title available?)
• On transportation polytopes with the minimum number of k-faces
• The aggregate capacity of virtual resources – linear models
• Perturbation of central transportation polytopes of order kn n
• scientific article; zbMATH DE number 4183167 (Why is no real title available?)

This page was built for publication: On the number of faces of certain transportation polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1580679)