3
$\begingroup$

Within paper ON THE COMPLEXITY OF TIMETABLE AND MULTI-COMMODITY FLOW PROBLEMS

there's a proof that the multi-commodity is NP-hard.

While in Multicommodity flows over time: Efficient algorithms and complexity

authors states that "[...] the only known polynomial-time algorithms for static multicommodity flow computations require general linear programming techniques".

They use word "static" only to differ from its time-dependent version. But I think it is the same problem considered in the first paper. Authors also refer to its complexity with the wording "poly($\simeq$LP)".

Can someone help me understand the right way of reading this apparent contradiction?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

"ON THE COMPLEXITY OF TIMETABLE AND MULTI-COMMODITY FLOW PROBLEMS" talks about integral flow while "Multicommodity flows over time: Efficient algorithms and complexity" does not. The integrality constraint (flows being integer valued) is important see LP vs ILP.

Improve this answer
$\endgroup$

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.