Approximation algorithm for maximum flow network interdiction problem

We consider the maximum flow network interdiction problem. We provide a new interpretation of the problem and define a concept called ”optimalcut”. We propose a heuristic algorithm to obtain an approximated cut, and we also obtain its error bound. Finally, we show that our heuristic is an α-approximation algorithm for a class of networks. By implementing it on three network types, we show the advantage of it over solving the model by CPLEX.

کلیدواژه ها:

Interdiction ‎ ، ‎ Approximation algorithm ‎ ، ‎ Network flow ‎ ، ‎ Minimum capacity cut