Characterization and algorithms for greedily solvable transportation problems

Abstract

We study transportation problems in which shipping between certain sources and destinations is disallowed. Given such a problem we seek a permutation of the decision variables which, when used by 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 a necessary and sufficient condition under which a permutation satisfies that requirement, and devise an efficient algorithm which constructs such a permutation or determines that none exist. Our characterization and the algorithm are based on Hoffman's notion of Monge sequences, as denned for the special case when no shippings are disallowed, and on an antimatroid interpretation of this notion. 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. Having constructed such a permutation, a solution of any problem with that cost matrix can be obtained in linear time.