Approximation algorithm for maximum flow network interdiction problem

Author(s):

Maria Afsharirad*

Message:
Article Type:
Research/Original Article (دارای رتبه معتبر)
Abstract:

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.

Keywords:

Interdiction , Approximation algorithm , Network flow , Minimum capacity cut

Language:
Persian
Published:
Iranian Journal of Numerical Analysis and Optimization, Volume:10 Issue: 1, Winter and Spring 2020
Pages:
1 to 18
https://www.magiran.com/p2107999