Extreme points of transportation polytope - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T19:06:08Z http://mathoverflow.net/feeds/question/75873 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/75873/extreme-points-of-transportation-polytope Extreme points of transportation polytope Memming 2011-09-19T16:47:24Z 2012-04-12T14:07:26Z <p>I'm interested in $n \times m$ joint probability tables with prescribed row and column marginals. Such tables form a convex set known as the <em>transportation polytope</em>. What are the extreme points of this set?</p> <p>For example, for a $2 \times 2$ case of $$\begin{bmatrix} x_{11} &amp; x_{12}\\ x_{21} &amp; x_{22} \end{bmatrix}$$ with row constraint $x_{11} + x_{12} = 0.9$, column constraint $x_{11} + x_{21} = 0.8$, and $\sum_{i,j} x_{ij} = 1$, then there are two extreme points, $$\begin{bmatrix} 0.8 &amp; 0.1\\ 0 &amp; 0.1 \end{bmatrix}, \quad \begin{bmatrix} 0.7 &amp; 0.2\\ 0.1 &amp; 0 \end{bmatrix}.$$ And every joint table with the constraint lies in the convex hull of these two points.</p> <p>Is there a general way of finding the extreme points? In other words, is there a generalization to Birkhoffâ€“von Neumann theorem for this case?</p> http://mathoverflow.net/questions/75873/extreme-points-of-transportation-polytope/75905#75905 Answer by Brendan McKay for Extreme points of transportation polytope Brendan McKay 2011-09-20T03:23:48Z 2011-09-20T03:54:30Z <p>A complete solution with references can be found in Section 8.1 of Brualdi, Combinatorial Matrix Classes, Cambridge University Press, 2006.</p> <p>Here is how to make an extreme point, and all extreme points can be made in this way. Suppose <code>$\{r_i\}$</code> and <code>$\{c_j\}$</code> are the required row and column sums. Start with a zero matrix $A=(a_{ij})$. Choose $i,j$ so that $r_i,c_j>0$. Set $a_{ij}=\min(r_i,c_j)$ and subtract $\min(r_i,c_j)$ from both $r_i$ and $c_j$. Keep doing this until all the row sums or all the columns sums are zero (and it better be both of them zero or there is no such matrix).</p> <p>And a characterization. For any matrix in the class you can define a bipartite graph with $m$ row-vertices and $n$ column-vertices where the edges indicate where the matrix entries are non-zero. Then the matrix is an extreme point iff the graph has no cycles.</p> http://mathoverflow.net/questions/75873/extreme-points-of-transportation-polytope/93868#93868 Answer by mcuturi for Extreme points of transportation polytope mcuturi 2012-04-12T14:07:26Z 2012-04-12T14:07:26Z <p>The answer above is partially wrong. The kind of extreme points which are obtained through the construction above, known as the northwest corner rule, can only generate a subset of extreme points (not all of them) of the polytope. To be more precise, the northwest rule can only generate those extreme points for which the graph (as described in the bottom of the answer above) is a caterpillar tree, as can be checked further here: <a href="http://www.newton.ac.uk/preprints/NI02033.pdf" rel="nofollow">http://www.newton.ac.uk/preprints/NI02033.pdf</a></p>