Given a graph $G$ and $K$ commodities to route from source to destination. I want to find, what is the maximum beneficial flow for each of the commodities and the relevant paths. I understand the problem in general falls under NPC, hence I am looking for FPTAS algorithms.

I am struggling with the problem, so any intuitive idea to tackle the problem is also most welcome.

  • $\begingroup$ What research have you done? The wikipedia page for multi-commodity flow claims to have a reference to a FPTAS for the problem, if fractional flows are allowed: en.wikipedia.org/wiki/Multi-commodity_flow_problem. You don't specify whether you're OK with fractional flows. If not, you could try applying randomized rounding. $\endgroup$ – D.W. Jan 27 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.