I can't get the difference between this two problems, which seem equal to me.

But, for the former, a polynomial solver is known, while, for the latter, it is not.

EDIT - References:

The quickest transhipment problem - by B. Hoppe and E. Tardos
The quickest multicommodity flow problem - by L. Fleischer and M. Skutella

In the former paper, which has polynomial solution, authors explicitly refer to integral flows. While in the latter one, authors state that "the complexity of the quickest multicommodity flow problem is still open. It has neither been proved to be NP-hard nor is it known to be solvable in polynomial time".

  • $\begingroup$ Please describe both problems, or add a link with some references. $\endgroup$
    – Kuifje
    Commented Oct 6, 2021 at 14:05
  • $\begingroup$ Done. Does it sound now? $\endgroup$ Commented Oct 6, 2021 at 14:19
  • $\begingroup$ Could you please refer with page number and paper name where you get the claims, you make? $\endgroup$ Commented Oct 6, 2021 at 15:10
  • $\begingroup$ May the answer simply be that the transshipment problem does not require a one-to-one connection between sources and sinks? $\endgroup$ Commented Oct 6, 2021 at 15:18


Your Answer

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

Browse other questions tagged or ask your own question.