<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>8234</id>
    <completedYear/>
    <publishedYear>2021</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2021-05-25</completedDate>
    <publishedDate>2021-05-25</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">On the Complexity of Computing Maximum and Minimum Min‐Cost‐Flows</title>
    <abstract language="eng">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.</abstract>
    <parentTitle language="eng">Networks</parentTitle>
    <identifier type="doi">10.1002/net.22060</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="SubmissionStatus">epub ahead of print</enrichment>
    <enrichment key="AcceptedDate">10.05.2021</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-73359</enrichment>
    <author>Kai Hoppmann-Baum</author>
    <submitter>Kai Hoppmann-Baum</submitter>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="hennig">Hoppmann, Kai</collection>
    <collection role="projects" number="MODAL-GasLab">MODAL-GasLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="enernet">Energy Network Optimization</collection>
    <collection role="institutes" number="Mathematical Algorithmic Intelligence">Mathematical Algorithmic Intelligence</collection>
    <collection role="institutes" number="aim">Applied Algorithmic Intelligence Methods</collection>
    <collection role="projects" number="MODAL-EnergyLab">MODAL-EnergyLab</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
</export-example>
