Combinatorics and geometry of transportation polytopes: an update
From MaRDI portal
Publication:3464532
zbMATH Open1360.90169arXiv1307.0124MaRDI QIDQ3464532FDOQ3464532
Authors: Jesús A. De Loera, Edward D. Kim 
Publication date: 27 January 2016
Abstract: A transportation polytope consists of all multidimensional arrays or tables of non-negative real numbers that satisfy certain sum conditions on subsets of the entries. They arise naturally in optimization and statistics, and also have interest for discrete mathematics because permutation matrices, latin squares, and magic squares appear naturally as lattice points of these polytopes. In this paper we survey advances on the understanding of the combinatorics and geometry of these polyhedra and include some recent unpublished results on the diameter of graphs of these polytopes. In particular, this is a thirty-year update on the status of a list of open questions last visited in the 1984 book by Yemelichev, Kovalev and Kravtsov and the 1986 survey paper of Vlach.
Full work available at URL: https://arxiv.org/abs/1307.0124
Recommendations
Combinatorics and topology in relation with holomorphic dynamical systems (37F20) Transportation, logistics and supply chain management (90B06) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)
Cited In (34)
- Full patterns in truncated transportation polytopes
- Pattern-avoiding polytopes
- Information-geometric equivalence of transportation polytopes
- Phase transition in random contingency tables with non-uniform margins
- On the diameter of cut polytopes
- On Dantzig figures from graded lexicographic orders
- The diameters of network-flow polytopes satisfy the Hirsch conjecture
- Wasserstein Barycenters Are NP-Hard to Compute
- Geometry of discrete copulas
- On the closest point to the origin in transportation polytopes
- Supercharacter theories of type \(A\) unipotent radicals and unipotent polytopes
- Supercharacter theories of type \(A\) unipotent radicals and unipotent polytopes
- Optimal nonparametric testing of missing completely at random and its connections to compatibility
- Quadratic diameter bounds for dual network flow polyhedra
- On the vertices of the \(d\)-dimensional Birkhoff polytope
- Transportation problems and simplicial polytopes that are not weakly vertex-decomposable
- A quick estimate for the volume of a polyhedron
- The Eulerian transformation
- The value function of a transportation problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- Coupling matrix manifolds assisted optimization for optimal transport problems
- Sign matrix polytopes from Young tableaux
- Good clusterings have large volume
- Hardness results for multimarginal optimal transport problems
- Orthogonal bases for transportation polytopes applied to Latin squares, magic squares and sudoku boards
- On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond
- Restricted Birkhoff polytopes and Ehrhart period collapse
- Topics of polyhedral combinatorics in transportation problems with exclusions
- On multi-symmetric functions and transportation polytopes
- Plethysm and lattice point counting
- The hierarchy of circuit diameters and transportation polytopes
- Lower bounds for contingency tables via Lorentzian polynomials
- Tropical medians by transportation
This page was built for publication: Combinatorics and geometry of transportation polytopes: an update
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3464532)
