Efficient algorithms for the hitchcock transportation problem

Abstract

We consider the Hitchcock transportation problem on n supply points and κ demand points when n is much greater than κ. The problem is solved in O(n2κ log n + n2 log2 n) time if we directly apply an efficient minimum-cost flow algorithm. We show that the complexity can be improved to O(κ2n log2 n) time if n > κ log κ. Further, applying a geometric method named splitter finding and randomization, we improve the time complexity for a case in which the ratio c of the least supply and the maximum supply satisfies the inequality log cn < n/κ4log n. Indeed, if n > κ5 log3 κ and c = poly(n), the problem is solved in O(κn) time, which is optimal.