Efficient Algorithms for the Hitchcock Transportation Problem
Takeshi Tokuyama, Jun Nakano · SIAM Journal on Computing · 1995
We consider the Hitchcock transportation problem on n supply points and k demand points when n is much greater than k. The problem can be solved in $O(kn^{2} \log n + n^{2}\log^{2} n)$ time if an efficient minimum-cost flow algorithm is directly applied. Applying a geometric method named splitter finding and a randomization technique, we can improve the time complexity when the ratio c of the maximum supply to the minimum supply is sufficiently small. The expected running time of our randomized algorithm is $O(\frac{kn\log cn}{\log(n/k^{4} \log^{2}k)})$ if $n > k^{4} \log^{2} k$, and $O(k^{5} \log^{2} n \log cn )$ if $n \leq k^{4} \log^{2} k$. If $n = \Omega (k^{4+\epsilon}) (\epsilon > 0)$ and $c = \operatorname{poly}(n)$, the problem is solved in $O(kn)$ time, which is optimal.