A faster polynomial algorithm for the unbalanced Hitchcock transportation problem

摘要

We present a new algorithm for the Hitchcock transportation problem. On instances with n sources and k sinks, our algorithm has a worst-case running time of O(nk(2)(log n + k log k)). It closes a gap between algorithms with running time linear in n but exponential in k and a polynomialtime algorithm with running time O(nk(2) log(2) n). (C) 2008 Elsevier B.V. All rights reserved.