0
$\begingroup$

Consider a $n,n$ transportation problem with two $d$ dimensional integral vectors $r$ and $c$ with the same total sum.

The Northwestern corner rule is a simple way to create a basic feasible solution to the transportation problem, that is find an integral matrix $X$ with row-sum equal to $r$ and column-sum equal to $c$.

Described with examples here, the rule iteratively creates a transportation table $$X=[x_{ij}]_{i,j\leq d}$$ between $r$ and $c$ by going through the following steps (paraphrasing the bottom of Page 2 of this preprint by L. Stougie):

The rule starts by giving the highest possible value to $x_{11}$, and at each step when a highest possible value is given to entry $x_{ij}$ it moves on to $x_{ij+1}$ in case $x_{ij}$ filled column $j$, or to $x_{i+1j}$ in case $x_{ij}$ filled row $i$, and proceeds until $x_{nn}$ has received a value.

L. Stougie makes the remark at the bottom of Page 2 that any row or column permutation (that is in the order of $r$ or $c$) yields a unique Northwestern solution, but that there exists an exponential number of row/column permutations that may share the same Northwestern solution.

My question is: do we know what that number is?

Although I can imagine from a combinatorial point of view why this number may grow exponentially (suppose $d\geq 5$ that $r$ starts as $r=[5,\cdots]$ and $c$ as $c=[1,1,1,1,1,...]$ then there are at least $5!$ different permutations of the order of $c$ that will leave the Northwestern solution unchanged) I wonder if there is a way to compute this number exactly?

Improve this question
$\endgroup$
3
  • $\begingroup$ If I don't misunderstand it, for all row and column sums equal to 1, every permutation matrix can be made. This gives $d!$ solutions. An upper bound would be the number of caterpillar forests. $\endgroup$
    – Brendan McKay
    Commented May 30, 2012 at 5:53
  • $\begingroup$ The number of caterpillar forests is indeed an upper bound on the number of NWC solutions, since the graph corresponding to a NWC solution is a caterpillar forest. My question is more simple (I think): given $r$, $c$ and corresponding solution NWC solution $X$, how many row and column permutations of $r$ and $c$ correspond to that solution? $\endgroup$
    – mcuturi
    Commented May 30, 2012 at 7:22
  • $\begingroup$ Brendan, many thanks for your first comment. Thinking aloud now: consider the partial sums $R_i=\sum_{k=1}^d r_i$ and define $C_i$ accordingly. We can consider $n(X)$ column permutations that leave $X$ unchanged, where $n(X)= \prod_{j=1}^{d-1} p_j!$ where $p_j=\text{card}\{ i| 1\leq i \leq d, R_{j} \leq C_i < R_{j+1}\}$. I am not sure this is enough though... $\endgroup$
    – mcuturi
    Commented May 30, 2012 at 8:23

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .