A faster polynomial algorithm for the unbalanced Hitchcock transportation problem

We present a new algorithm for the Hitchcock transportation problem. On instances with nn sources and kk sinks, our algorithm has a worst-case running time of O(nk2(logn+klogk))O(nk2(logn+klogk)). It closes a gap between algorithms with running time linear in nn but exponential in kk and a polynomial-time algorithm with running time O(nk2log2n)O(nk2log2n).