TY - JOUR

T1 - A (B+1)-approximation for network flow interdiction with unit costs

AU - Boeckmann, Jan

AU - Thielen, Clemens

N1 - Publisher Copyright:
© 2021 The Author(s)

PY - 2024/9/15

Y1 - 2024/9/15

N2 - In the network flow interdiction problem (NFI), an interdictor aims to remove arcs of total cost at most a given budget B from a network with given arc costs and capacities such that the value of a maximum flow from a source s to a sink t is minimized. We present a polynomial-time (B+1)-approximation algorithm for NFI with unit arc costs, which is the first approximation algorithm for any variant of network flow interdiction whose approximation ratio only depends on the budget available to the interdictor, but not on the size of the network.

AB - In the network flow interdiction problem (NFI), an interdictor aims to remove arcs of total cost at most a given budget B from a network with given arc costs and capacities such that the value of a maximum flow from a source s to a sink t is minimized. We present a polynomial-time (B+1)-approximation algorithm for NFI with unit arc costs, which is the first approximation algorithm for any variant of network flow interdiction whose approximation ratio only depends on the budget available to the interdictor, but not on the size of the network.

KW - Approximation algorithm

KW - Interdiction problem

KW - Network flow interdiction

UR - http://www.scopus.com/inward/record.url?scp=85111482429&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2021.07.008

DO - 10.1016/j.dam.2021.07.008

M3 - Article

AN - SCOPUS:85111482429

SN - 0166-218X

VL - 354

SP - 58

EP - 71

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -