Extreme points of general transportation polytopes

2024/04/25 by Patrice Koehl, Koehl, Patrice
Engineering · Mathematics · #05C50 #Advanced Theoretical and Applied Studies in Material Sciences and Geometry #Combinatorics (math.CO) #FOS: Mathematics #G.2.1 #Mathematics and Applications

paper · pdf · doi:10.48550/arxiv.2404.16791

openalex publication_date 2024/04/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Transportation matrices are m× n non-negative matrices whose row sums and row columns are equal to, or dominated above with given integral vectors R and C. Those matrices belong to a convex polytope whose extreme points have been previously characterized. In this article, a more general set of non-negative transportation matrices is considered, whose row sums are bounded by two integral non-negative vectors R_min and R_max and column sums are bounded by two integral non-negative vectors C_min and C_max. It is shown that this set is also a convex polytope whose extreme points are then fully characterized.

Related

• Combinatorics and Geometry of Transportation Polytopes: An Update
• Extreme points of matrix convex sets and their spanning properties
• Extreme points of the set of density matrices with positive partial transpose
• Geometric Combinatorics of Transportation Polytopes and the Behavior of the Simplex Method
• Asymptotic estimates for the number of contingency tables, integer flows, and volumes of transportation polytopes