A fast algorithm for constructing monge sequences in transportation problems with forbidden arcs

✍ Scribed by Ron Shamir

• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 688 KB
• Volume: 114
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(93)90382-4

✦ Synopsis

Shamir, R., A fast algorithm for constructing

Monge sequences in transportation problems with forbidden arcs, Discrete Mathematics 114 (1993) 435-444.

Given a cost matrix of the transportation problem and a permutation of the decision variables, we say that the problem is completely solvable by that permutation if the greedy algorithm, which maximizes each variable in turn according to the order prescribed by the permutation, provides an optimal solution for every feasible supply and demand vectors. We give an efficient algorithm which constructs such a permutation or determines that none exists. Our algorithm is based on Hoffman's notion of Monge sequence, which was recently extended by Dietrich (1990) to problems in which some of the arcs are forbidden. We also show that the existence of a Monge sequence is both necessary and sufficient for a problem to be completely solvable by any single permutation.

The running time of our algorithm is better than that of the best known algorithms for solving the transportation problem, both for sparse and for dense problems.