Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 3 von 9
Zurück zur Trefferliste

On the Complexity of the Maximum Minimum Cost Flow Problem

Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-73359
  • 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.

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
Verfasserangaben:Kai HoppmannORCiD
Dokumentart:ZIB-Report
Datum der Erstveröffentlichung:29.05.2019
Schriftenreihe (Bandnummer):ZIB-Report (19-19)
ISSN:1438-0064
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.