On the Complexity of Computing Maximum and Minimum Min‐Cost‐Flows
| Autor: | Kai Hoppmann-Baum |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
050210 logistics & transportation
Mathematical optimization 021103 operations research Computer Networks and Communications 05 social sciences 0211 other engineering and technologies 02 engineering and technology Directed graph Transportation theory Flow network Bilevel optimization Arc (geometry) Hardware and Architecture 0502 economics and business Value (economics) Minimum-cost flow problem Time complexity Software Information Systems Mathematics |
| Zdroj: | Networks. 79:236-248 |
| ISSN: | 1097-0037 0028-3045 |
| DOI: | 10.1002/net.22060 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text