Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1143057 | Operations Research Letters | 2008 | 6 Pages |
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).
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Ulrich Brenner,