Approximation algorithm for maximum flow network interdiction problem

Iranian Journal of Numerical Analysis and Optimization

مقاله 1، دوره 10، شماره 1 - شماره پیاپی 17، 2020، صفحه 1-18   

نوع مقاله: Research Article

شناسه دیجیتال (DOI): 10.22067/ijnao.v10i1.75392

نویسنده

M. Afsharirad^*

Department of Mathematics, University of Science and Technology of Mazandaran, P.O.Box: 48518-78195, Behshahr, Iran.

چکیده

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

مراجع