A faster polynomial algorithm for the unbalanced Hitchcock transportation problem

0.00 Avg rating—0 Votes

Article ID:	iaor20102854
Volume:	36
Issue:	4
Start Page Number:	408
End Page Number:	413
Publication Date:	Jul 2008
Journal:	Operations Research Letters
Authors:	Brenner Ulrich
Keywords:	Hitchcock problem

Abstract:

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²(logn+klogk)). It closes a gap between algorithms with running time linear in n but exponential in k and a polynomial-time algorithm with running time O(nk²log²n)

Reviews

Required fields are marked *. Your email address will not be published.