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

DOI10.1002/net.22060zbMath1528.90057OpenAlexW3164611929MaRDI QIDQ6065863

Kai Hoppmann-Baum

Publication date: 11 December 2023

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.22060

zbMATH Keywords

minimum cost flowbilevel programmingnetwork interdictionapproximation hardnessattacker-defender problemparametrized flow problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10)

Related Items (1)

Interval transportation problem: feasibility, optimality and the worst optimal value

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing technical capacities in the European entry-exit gas market is NP-hard
• Robust network optimization under polyhedral demand uncertainty is \(NP\)-hard
• Optimization, approximation, and complexity classes
• Practical bilevel optimization. Algorithms and applications
• Foundations of bilevel programming
• A survey of network interdiction models and algorithms
• Bookings in the European gas market: characterisation of feasibility and computational complexity results
• Finding Maximum Minimum Cost Flows to Evaluate Gas Network Capacities
• On approximation properties of the Independent set problem for degree 3 graphs

This page was built for publication: On the Complexity of Computing Maximum and Minimum Min‐Cost‐Flows