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.
Additional Services
| 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/10.1002/net.22060 |
