A strongly polynomial algorithm for the transportation problem

0.00 Avg rating—0 Votes

Article ID:	iaor1997717
Country:	Netherlands
Volume:	68
Issue:	1
Start Page Number:	1
End Page Number:	13
Publication Date:	Jan 1995
Journal:	Mathematical Programming
Authors:	Kleinschmidt P., Schannath H.
Keywords:	computational analysis

Abstract:

For the (linear) transportation problem with m supply nodes, n demand nodes and k feasible arcs the authors describe an algorithm which runs in time proportional to mlogm(k+nlogn) (assuming w.l.o.g. m≥n). The algorithm uses excess scaling. The complexity bound is a slight improvement over the bound achieved by an application of a min-cost-flow algorithm of Orlin to the transportation problem.

Reviews

Required fields are marked *. Your email address will not be published.