# Are there FPTASs for the min cost flow problem?

In literature, one can find many approximation algorithms for the multicommodity min cost flow problem or other variants of the standard single-commodity min cost flow problem. But are there FPTASs for the min cost flow problem?

Possibly, there is no need for an FPTAS here since an optimal solution can be computed very fast (using double scaling or the enhanced capacity scaling algorithm, for example). But from a theoretical point of view, this would be interesting to know.

• Yeah, that's what I'm looking for. Maybe there is an FPTAS with a running time like $\mathcal{O}(m \cdot n \cdot \frac{1}{\varepsilon})$ ? That would at least not be inferior to the polynomial time algorithms mentioned above. – user1742364 Nov 11 '14 at 13:27
You may want to look at "Adding Multiple Cost Constraints to Combinatorial Optimization Problems, with Applications to Multicommodity Flows" by David Karger and Serge Plotkin (STOC 1995). They find a $$(1+\epsilon)$$ approximation in $${\tilde O}(\epsilon^{-3}kmn)$$ time, where $$k$$ is the number of commodities, $$m$$ is the number of edges, and $$n$$ is the number of vertices in the input problem.