About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Conference paper
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.
Related
Conference paper
On minimum and maximum spanning trees of linearly moving points
Conference paper