Article ID Journal Published Year Pages File Type
1143057 Operations Research Letters 2008 6 Pages PDF
Abstract

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).

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,