Polynomial time interior point algorithms for transportation problems

This paper deals with the Hitchcock transportation problem with m supply points and n demand points. Assume that m•n and all the data are positive integers which are less than or equal to an integer M. It proposes two polynomial time algorithms for solving the problems. The algorithms are based on the interior point algorithms for solving general linear programming problems. Using some features of the transportation problems, this paper decreases the computational complexities. It shows that one of the algorithms requires at most O(m³n²lognM+n³) arithmetic operations and the other requires at most O(n⁴lognM) arithmetic operations.