On the Complexity of Computing Maximum and Minimum Min‐Cost‐Flows

epub ahead of print
  • Consider a flow network, i.e., a directed graph where each arc has a nonnegative capacity value and an associated length, together with nonempty supply intervals for the sources and nonempty demand intervals for the sinks. The Maximum Min-Cost-Flow Problem (MaxMCF) is to find fixed supply and demand values within these intervals such that the optimal objective value of the induced Min-Cost-Flow Problem (MCF) is maximized. In this paper, we show that MaxMCF as well as its uncapacitated variant, the Maximum Transportation Problem (MaxTP), are NP-hard. Further, we prove that MaxMCF is APX-hard if a connectedness-condition regarding the sources and the sinks of the flow network is dropped. Finally, we show how the Minimum Min-Cost-Flow Problem (MinMCF) can be solved in polynomial time.
Metadaten
Author:Kai Hoppmann-BaumORCiD
Document Type:Article
Parent Title (English):Networks
Date of first Publication:2021/05/25
Preprint:urn:nbn:de:0297-zib-73359
DOI:https://doi.org/https://doi.org/10.1002/net.22060