On the Complexity and Approximability of Budget-Constrained Minimum Cost Flows

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 edge, whose total value in a feasible flow is constrained by a given budget B. This...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2016-07
Main Authors: Holzhauser, Michael, Krumke, Sven O, Thielen, Clemens
Format: Article
Language:English
Subjects:
Budgeting
Budgets
Complexity
Cost engineering
Game theory
Graphs
Minimum cost
Polynomials
Upper bounds
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 edge, whose total value in a feasible flow is constrained by a given budget B. This problem can, e.g., be seen as the application of the {\epsilon}-constraint method to the bicriteria minimum cost flow problem. We show that we can solve the problem exactly in weakly polynomial time \(O(\log M \cdot 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 occuring 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.
ISSN:2331-8422