1
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\begingroup$ Please describe both problems, or add a link with some references. $\endgroup$
    – Kuifje
    Oct 6, 2021 at 14:05
  • $\begingroup$ Done. Does it sound now? $\endgroup$
    – Daniele Cuomo
    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$
    – worldsmithhelper
    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$
    – Daniele Cuomo
    Oct 6, 2021 at 15:18

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.