×

Budget-constrained minimum cost flows. (English) Zbl 1347.90081

Summary: 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}}\)-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 (cf. [D. S. Hochbaum and A. Segev, Networks 19, No. 3, 291–312 (1989; Zbl 0673.90035)])), is strongly \({\mathcal{NP}}\)-hard to solve and we adapt several results from the integral case.

MSC:

90C35 Programming involving graphs or networks
90C59 Approximation methods and heuristics in mathematical programming

Citations:

Zbl 0673.90035
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows. Prentice Hall, Network Flows · Zbl 1201.90001
[2] Ahuja RK, Orlin JB (1995) A capacity scaling algorithm for the constrained maximum flow problem. Networks 25(2):89-98 · Zbl 0821.90041 · doi:10.1002/net.3230250207
[3] Bein WW, Brucker P, Tamir A (1985) Minimum cost flow algorithms for series-parallel networks. Discret Appl Math 10:117-124 · Zbl 0571.90019 · doi:10.1016/0166-218X(85)90006-X
[4] Booth H, Tarjan RE (1992) Finding the minimum-cost maximum flow in a series-parallel network. J Algorithms 15:416-446 · Zbl 0795.90018 · doi:10.1006/jagm.1993.1048
[5] Burkard RE, Dlaska K, Klinz B (1993) The quickest flow problem. Z für Oper Res 37(1):31-58 · Zbl 0780.90031
[6] Chankong V, Haimes YY (2008) Multiobjective decision making: theory and methodology., Dover books on engineering seriesDover Publications, Incorporated, New York · Zbl 1217.91053
[7] Demgensky I, Noltemeier H, Wirth HC (2002) On the flow cost lowering problem. Eur J Operat Res 137(2):265-271 · Zbl 0998.90069 · doi:10.1016/S0377-2217(01)00208-9
[8] Demgensky I, Noltemeier H, Wirth HC (2004) Optimizing cost flows by edge cost and capacity upgrade. J Discret Algorithms 2(4):407-423 · Zbl 1118.90052 · doi:10.1016/j.jda.2004.04.003
[9] Maya Duque PA, Coene S, Goos P, Sörensen K, Spieksma F (2013) The accessibility arc upgrading problem. Eur J Operat Res 224(3):458-465 · Zbl 1292.90071 · doi:10.1016/j.ejor.2012.09.005
[10] Ehrgott M (2005) Multicriteria optimization, 2nd edn. Springer, Berlin · Zbl 1132.90001
[11] Garey MR, Johnson DS (1979) Computers and intractability—a guide to the theory of \[{\cal NP}\] NP-completeness. W.H. Freeman and Company, New York · Zbl 0411.68039
[12] Geoffrion AM (1967) Solving bicriterion mathematical programs. Operat Res 15(1):39-54 · Zbl 0173.21602 · doi:10.1287/opre.15.1.39
[13] Han Y, Pan V, Reif J (1992) Efficient parallel algorithms for computing all pair shortest paths in directed graphs. In: Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, ACM, pp. 353-362 · Zbl 0478.68065
[14] Hochbaum DS, Segev A (1989) Analysis of a flow problem with fixed charges. Networks 19(3):291-312 · Zbl 0673.90035 · doi:10.1002/net.3230190304
[15] Kellerer H, Pferschy U, Pisinger D (2004) Knapsack problems. Springer, Berlin · Zbl 1103.90003 · doi:10.1007/978-3-540-24777-7
[16] Krumke SO, Schwarz S (1998) On budget-constrained flow improvement. Inf Process Lett 66(6):291-297 · Zbl 1078.68641 · doi:10.1016/S0020-0190(98)00070-2
[17] Krumke SO, Marathe MV, Noltemeier H, Ravi R, Ravi SS (1998) Approximation algorithms for certain network improvement problems. J Comb Optim 2(3):257-288 · Zbl 0916.90261 · doi:10.1023/A:1009798010579
[18] Megiddo N (1979) Combinatorial optimization with rational objective functions. Math Operat Res 4(4):414-424 · Zbl 0425.90076 · doi:10.1287/moor.4.4.414
[19] Megiddo N (1983) Applying parallel computation algorithms in the design of serial algorithms. JACM 30(4):852-865 · Zbl 0627.68034 · doi:10.1145/2157.322410
[20] Schrijver A (1998) Theory of linear and integer programming. Wiley, Chichester · Zbl 0970.90052
[21] Spellman FR (2013) Handbook of water and wastewater treatment plant operations, 3rd edn. Taylor & Francis, Boca Raton · doi:10.1201/b15579
[22] Valdes J, Tarjan RE, Lawler E (1982) The recognition of series parallel digraphs. SIAM J Comput 11:298-313 · Zbl 0478.68065 · doi:10.1137/0211023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.