An algorithm for the detection and construction of Monge sequences (Q1116656): Difference between revisions

\textit{A. J. Hoffman} [Proc. Symp. Pure Math. 7, 317-327 (1963; Zbl 0171.178)] proved that a transportation problem can be solved by a greedy algorithm if there exists a sequence (called Monge sequence) of pairs of indices of the cost matrix \(C=(c_{ij})\) such that if (i,j) preceeds both (i,s) and (r,j), then \(c_{ij}+c_{rs}\leq c_{is}+c_{rj}.\) The authors describe a general algorithm which generates a Monge sequence whenever it exists and prove that for an \(m\times n\) matrix \({\mathcal C}\) it requires \(O(\bar m^ 2\bar n \log \bar n)\) time and \(O(\bar m^ 2\bar n)\) space where \(\bar m=\min (m,n)\) and \(\bar n=\max (m,n).\)