2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

If an optimal solution can be calculated in polynomial time, then the same algorithm gives you an FPTAS.

There might, however, be quasilinear time algorithms which give better and better approximations, running faster than algorithms for computing the min cost flow exactly.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user1742364 Nov 11 '14 at 13:27
0
$\begingroup$

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.

$\endgroup$

Your Answer

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

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