Budget-constrained minimum cost flows

Michael Holzhauser (), Sven O. Krumke () and Clemens Thielen ()
Additional contact information
Michael Holzhauser: University of Kaiserslautern
Sven O. Krumke: University of Kaiserslautern
Clemens Thielen: University of Kaiserslautern

Journal of Combinatorial Optimization, 2016, vol. 31, issue 4, No 24, 1720-1745

Abstract: Abstract We study an extension of the well-known minimum cost flow problem in which a second kind of costs (called usage fees) is associated with each edge. The goal is to minimize the first kind of costs as in traditional minimum cost flows while the total usage fee of a flow must additionally fulfill a budget constraint. We distinguish three variants of computing the usage fees. The continuous case, in which the usage fee incurred on an edge depends linearly on the flow on the edge, can be seen as the $$\varepsilon $$ ε -constraint method applied to the bicriteria minimum cost flow problem. We present the first strongly polynomial-time algorithm for this problem. In the integral case, in which the fees are incurred in integral steps, we show weak $${\mathcal {NP}}$$ NP -hardness of solving and approximating the problem on series-parallel graphs and present a pseudo-polynomial-time algorithm for this graph class. Furthermore, we present a PTAS, an FPTAS, and a polynomial-time algorithm for several special cases on extension-parallel graphs. Finally, we show that the binary case, in which a fixed fee is payed for the usage of each edge independently of the amount of flow (as for fixed cost flows—Hochbaum and Segev in Networks 19(3):291–312, 1989), is strongly $${\mathcal {NP}}$$ NP -hard to solve and we adapt several results from the integral case.

Keywords: Algorithms; Complexity; NP-completeness; Minimum cost flow; Network improvement (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-015-9865-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:31:y:2016:i:4:d:10.1007_s10878-015-9865-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-015-9865-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().