Hardness and approximation for network flow interdiction
From MaRDI portal
Abstract: In the Network Flow Interdiction problem an adversary attacks a network in order to minimize the maximum s-t-flow. Very little is known about the approximatibility of this problem despite decades of interest in it. We present the first approximation hardness, showing that Network Flow Interdiction and several of its variants cannot be much easier to approximate than Densest k-Subgraph. In particular, any -approximation algorithm for Network Flow Interdiction would imply an -approximation algorithm for Densest k-Subgraph. We complement this hardness results with the first approximation algorithm for Network Flow Interdiction, which has approximation ratio 2(n-1). We also show that Network Flow Interdiction is essentially the same as the Budgeted Minimum s-t-Cut problem, and transferring our results gives the first approximation hardness and algorithm for that problem, as well.
Recommendations
- An approximation algorithm for network flow interdiction with unit costs and two capacities
- Network flow interdiction on planar graphs
- Approximation algorithm for maximum flow network interdiction problem
- scientific article; zbMATH DE number 4055051
- The maximum flow network interdiction problem: valid inequalities, integrality gaps, and approximability
- Network interdiction and stochastic integer programming
- Approximation and Online Algorithms
- Flow Problems in Multi-Interface Networks
- On the computational behavior of a polynomial-time network flow algorithm
- Combined Competitive Flow Control and Routing in Networks with Hard Side Constraints
Cited in
(39)- Filtering undesirable flows in networks
- Protection of flows under targeted attacks
- Parametric multiroute flow and its application to multilink-attack network
- Blocking optimal structures
- An approximation algorithm for network flow interdiction with unit costs and two capacities
- Interdicting facilities in tree networks
- The maximum flow network interdiction problem: valid inequalities, integrality gaps, and approximability
- The complexity of computing a robust flow
- On the hardness of approximating the min-hack problem
- Preventing small \(\mathbf{(s,t)} \)-cuts by protecting edges
- Theoretical and computational advances for network diversion
- Interdiction problems on planar graphs
- 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?)
- Packing interdiction and partial covering problems
- Symmetric interdiction for matching problems
- Sherali-Adams integrality gaps matching the log-density threshold
- Maximizing convergence time in network averaging dynamics subject to edge removal
- A Progressive Approximation Approach for the Exact Solution of Sparse Large-Scale Binary Interdiction Games
- A Scalable Lower Bound for the Worst-Case Relay Attack Problem on the Transmission Grid
- Improved Algorithms for MST and Metric-TSP Interdiction
- Improved hardness for cut, interdiction, and firefighter problems
- Rerouting Flows when Links Fail
- Analysis of budget for interdiction on multicommodity network flows
- Approximability of the k‐server disconnection problem
- Vertex downgrading to minimize connectivity
- On the minimum \(s-t\) cut problem with budget constraints
- Sum-of-squares lower bounds for densest k-subgraph
- A (B + 1)-approximation for network flow interdiction with unit costs
- An exact method for nonlinear network flow interdiction problems
- Approximation algorithms for two extensions of min-k-union
- Robust static and dynamic maximum flows
- On extensions of min-k-union
- An FPTAS for connectivity interdiction
- An FPTAS for connectivity interdiction
- On short paths interdiction problems: Total and node-wise limited interdiction
- Network flow interdiction on planar graphs
This page was built for publication: Hardness and approximation for network flow interdiction
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4638580)
