7335
eng
reportzib
0
--
2019-05-29
--
On the Complexity of the Maximum Minimum Cost Flow Problem
Consider a flow network, i.e., a directed graph where each arc has a nonnegative capacity and an associated length, together with nonempty supply-intervals for the sources and nonempty demand-intervals for the sinks. The goal of the Maximum Minimum Cost Flow Problem (MMCF) is to find fixed supply and demand values within these intervals, such that the optimal objective value of the induced Minimum Cost Flow Problem (MCF) is maximized. In this paper, we show that MMCF is APX-hard and remains NP-hard in the uncapacitated case.
1438-0064
urn:nbn:de:0297-zib-73359
Kai Hoppmann
Kai Hoppmann
ZIB-Report
19-19
Mathematical Optimization
Hoppmann, Kai
MODAL-GasLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/7335/complexity_paper.pdf