An approximation algorithm for network flow interdiction with unit costs and two capacities

DOI10.1007/978-3-030-63072-0_13MaRDI QIDQ2056900zbMATH OpenOpenAlexFDO

Authors Jan Boeckmann, Clemens Thielen

Publication date 8 December 2021

Full work available at URL https://doi.org/10.1007/978-3-030-63072-0_13

zbMATH Keywords

approximation algorithmnetwork flow interdictiontwo capacities

Mathematics Subject Classification ID

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

Recommendations

• Hardness and approximation for network flow interdiction
• Approximation algorithm for maximum flow network interdiction problem
• Network flow interdiction on planar graphs
• scientific article; zbMATH DE number 2050722
• The maximum flow network interdiction problem: valid inequalities, integrality gaps, and approximability

Cites work

• Deterministic network interdiction
• Hardness and approximation for network flow interdiction
• scientific article; zbMATH DE number 2050722 (Why is no real title available?)
• Interdicting structured combinatorial optimization problems with {0,1}-objectives
• Network flows. Theory, algorithms, and applications.
• Polynomial integrality gaps for strong SDP relaxations of densest k-subgraph
• Removing Arcs from a Network
• The network inhibition problem

Cited in

(9)

• Interdicting structured combinatorial optimization problems with {0,1}-objectives
• Approximation algorithm for maximum flow network interdiction problem
• Matrix interdiction problem
• scientific article; zbMATH DE number 2050722 (Why is no real title available?)
• Hardness and approximation for network flow interdiction
• Analysis of budget for interdiction on multicommodity network flows
• Shortest path interdiction problem with convex piecewise-linear costs
• A (B + 1)-approximation for network flow interdiction with unit costs
• Network flow interdiction on planar graphs

This page was built for publication: An approximation algorithm for network flow interdiction with unit costs and two capacities

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