Name
Abstract | ||
|---|---|---|
We consider a variant of the well-known minimum cost flow problem where the flow on each arc in the network is restricted to be either zero or above a given lower bound. The problem was recently shown to be weakly NP-complete even on series-parallel graphs. We start by showing that the problem is strongly NP-complete and cannot be approximated in polynomial time (unless P=NP) up to any polynomially computable function even when the graph is bipartite and the given instance is guaranteed to admit a feasible solution. Moreover, we present a pseudo-polynomial-time exact algorithm and a fully polynomial-time approximation scheme (FPTAS) for the problem on series-parallel graphs. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.ipl.2011.03.007 | Inf. Process. Lett. |
Keywords | Field | DocType |
weakly np-complete,polynomially computable function,polynomial-time approximation scheme,polynomial time,series-parallel graph,pseudo-polynomial-time exact algorithm,well-known minimum cost flow,feasible solution,minimum quantity,lower bound,computational complexity,minimum cost flow,fully polynomial time approximation scheme | Complete graph,Discrete mathematics,Combinatorics,Exact algorithm,Bipartite graph,Multi-commodity flow problem,Time complexity,Computable function,Minimum-cost flow problem,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
111 | 11 | 0020-0190 |
Citations | PageRank | References |
5 | 0.66 | 3 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sven O. Krumke | 1 | 308 | 36.62 |
| Clemens Thielen | 2 | 75 | 15.11 |