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

DOI10.1007/978-3-030-63072-0_13zbMATH Open1479.90043OpenAlexW3135388429MaRDI QIDQ2056900FDOQ2056900

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

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

zbMATH Keywords

approximation algorithmnetwork flow interdictiontwo capacities

Mathematics Subject Classification ID

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

Cites Work

• Network flows. Theory, algorithms, and applications.
• Deterministic network interdiction
• Removing Arcs from a Network
• Polynomial integrality gaps for strong SDP relaxations of densest \(k\)-subgraph
• The network inhibition problem
• Title not available (Why is that?)
• Hardness and approximation for network flow interdiction
• Interdicting structured combinatorial optimization problems with {0,1}-objectives

Cited In (9)

• A \((B + 1)\)-approximation for network flow interdiction with unit costs
• Title not available (Why is that?)
• Interdicting structured combinatorial optimization problems with {0,1}-objectives
• Approximation algorithm for maximum flow network interdiction problem
• Network flow interdiction on planar graphs
• Matrix interdiction problem
• Shortest path interdiction problem with convex piecewise-linear costs
• Hardness and approximation for network flow interdiction
• Analysis of budget for interdiction on multicommodity network flows

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)