13
$\begingroup$

Consider the well known transportation problem: There are $m$ supply nodes, $n$ demand nodes and $k$ feasible arcs. Every node has a integer supply or demand, and the arcs have integer costs, used linearly, i.e. if $x$ units are shipped along an edge annotated with $c$, the cost is $c\cdot x$.

I have an article by Kleinschmidt and Schannath describing an $O(m\log m (k+n\log n))$ solution.

Is this the currently best algorithm, or has there been an improvement since 1995?

(My search turned up an article by Brenner from 2008, but I don't have access to it. The title talks about the "unbalanced Hitchcock transportation problem", I am not sure it is the problem considered here).

Would this be the right algorithm to implement?

Which libraries provide implementations of the transportation problem?

Improve this question
$\endgroup$
1
  • $\begingroup$ do you need integer transportation or is fractional transportation ok (because the latter is the EMD, is it not ?) $\endgroup$
    – Suresh Venkat
    Commented Mar 31, 2012 at 17:39

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.