Stronger hardness for maximum robust flow and randomized network interdiction

DOI10.1007/978-3-032-28691-8_3MaRDI QIDQ7349442zbMATH OpenFDO

Authors Jannik Matuschke

Publication date 16 September 2026

Full work available at URL https://doi.org/10.1007/978-3-032-28691-8_3

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27)

Cites work

• Completeness in the polynomial hierarchy for many natural problems in bilevel and robust optimization
• Deterministic network interdiction
• Hardness and approximation for network flow interdiction
• Improved region-growing and combinatorial algorithms for k-route cut problems (extended abstract)
• Maximizing residual flow under an arc destruction
• More complicated questions about maxima and minima, and some closures of NP
• Network flow interdiction on planar graphs
• On multiroute maximum flows in networks.
• On the complexity of recoverable robust optimization in the polynomial hierarchy
• On the hardness of approximating minimization problems
• On the power of randomization in network interdiction
• On truth-table reducibility to SAT
• Parametric multiroute flow and its application to multilink-attack network
• Propositional truth maintenance systems: Classification and complexity analysis
• Protection of flows under targeted attacks
• Rerouting Flows when Links Fail
• Robust and adaptive network flows
• Robust discrete optimization and network flows
• Robust flows over time: models and complexity results
• The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
• The complexity of computing a robust flow
• The maximum residual flow problem: NP‐hardness with two‐arc destruction

This page was built for publication: Stronger hardness for maximum robust flow and randomized network interdiction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7349442)