Budgetconstrained minimum cost flows

Authors: Michael Holzhauser Sven O Krumke Clemens Thielen

Publish Date: 2015/03/25

Volume: 31, Issue: 4, Pages: 1720-1745

PDF Link

Abstract

We study an extension of the wellknown 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 polynomialtime algorithm for this problem In the integral case in which the fees are incurred in integral steps we show weak mathcal NPhardness of solving and approximating the problem on seriesparallel graphs and present a pseudopolynomialtime algorithm for this graph class Furthermore we present a PTAS an FPTAS and a polynomialtime algorithm for several special cases on extensionparallel 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 193291–312 1989 is strongly mathcal NPhard to solve and we adapt several results from the integral caseWe thank the anonymous referees for their valuable comments and suggestions Furthermore we thank Stefan Schwarz for his suggestions on the proof of Theorem 8 This work was partially supported by the German Federal Ministry of Education and Research within the project “SinOptiKom—Crosssectoral Optimization of Transformation Processes in Municipal Infrastructures in Rural Areas”

Keywords: