# FPTAS algorithm to find flow at each link for multi commodity flow problem?

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.

• 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. – D.W. Jan 27 at 17:05