Name
Abstract | ||
|---|---|---|
We investigate the complexity and approximability of the budget-constrained minimum cost flow problem, which is an extension of the traditional minimum cost flow problem by a second kind of costs associated with each arc, whose total value in a feasible flow is constrained by a given budget B. This problem appears both in practical applications and as a subproblem when applying the ε-constraint method to the bicriteria minimum cost flow problem. We show that we can solve the problem exactly in weakly polynomial time O(logM⋅MCF(m,n,C,U)), where C, U, and M are upper bounds on the largest absolute cost, largest capacity, and largest absolute value of any number occurring in the input, respectively, and MCF(m,n,C,U) denotes the complexity of finding a traditional minimum cost flow. Moreover, we present two fully polynomial-time approximation schemes for the problem on general graphs and one with an improved running-time for the problem on acyclic graphs. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.ipl.2017.06.003 | Information Processing Letters |
Keywords | DocType | Volume |
Algorithms,Complexity,Minimum cost flow,Approximation | Journal | 126 |
ISSN | Citations | PageRank |
0020-0190 | 1 | 0.36 |
References | Authors | |
5 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael Holzhauser | 1 | 13 | 3.34 |
| Sven O. Krumke | 2 | 308 | 36.62 |
| Clemens Thielen | 3 | 75 | 15.11 |