Maria Afsharirad


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.

Article Details


Interdiction;, Approximation algorithm;, Network flow;, Minimum capacity cut.

[1] Afsharirad, M. and Taghizadeh, H. Maximum dynamic network flow interdiction problem: New formulation and solution procedures, Comput. Ind. Eng. 65(4) (2013), 531–536.
[2] Afsharirad, M. and Taghizadeh, H. Two extended formulations for car dinality maximum flow network interdiction problem, Networks, 69(4)(2017), 367–377.
[3] Altner, D.S., Ergun, O. and Uhan, N.A., The maximum flow network interdiction problem: valid inequalities, integrality gaps and approximability, Oper. Res. Lett., 38 (2010), 33–38.
[4] Assimakopoulos, N. A network interdiction model for hospital infection control, Computers in Biology and Medicine, 17 (1987), 413–422.
[5] Brown, G., Carlyle, M., Salmeron, J. and Wood, R.K. Defending critical infrastructure, Interfaces, 36(6) (2005), 530–544.
[6] Burch, C., Carr, R., Krumke, S., Marathe, M., Phillips, C. and Sundberg, E. A decomposition-based pseudoapproximation algorithm for network flow inhibition, Network interdiction and stochastic integer pro
gramming (Davis, CA, 2002), 51–68, Oper. Res./Comput. Sci. InterfacesSer., 22, Kluwer Acad. Publ., Boston, MA, 2003.
[7] Chestnut, S.R. and Zenklusen, R. Hardness and approximation for network flow interdiction, Networks, 69(4) (2017), 378-387.
[8] Church, R.L., Scaparra, M.P. and Middleton, R.S. Identifying critical infrastructure: The median and covering facility interdiction problems, Annals of the Association of American Geographers, 94 (2004), 491–502.
[9] Cormican, K.J., Morton, D.P., and Wood, R.K. , Stochastic network interdiction, Oper. Res., 46 (1998), 184–197.
[10] Durbin, E.P. An interdiction model of highway transportation, Santa Monica, CA: RAND Corporation, 1966.
[11] Granata, D., Steeger, G. and Rebennack, S. Network interdiction via a critical disruption path: Branch-and-price algorithms, Comput. Oper. Res., 40(11) (2013), 2689–2702.
[12] Lim, C. and Smith, J.C. Algorithms for discrete and continuous multi commodity flow network interdiction problems, IIE Transactions, 39(2007),15–26.
[13] Lunday, B.J. and Sherali, H.D. A dynamic network interdiction problem, Informatica, 21(4) (2010), 553–574.
[14] Lunday, B.J. and Sherali, H.D. Network interdiction to minimize the maximum probability of evasion with synergy between applied resources, Ann. Oper. Res. 196 (2012), 411–42.
[15] Miller, L.E. (2011), Catalog of network connectivity models, http://w3.antd.nist.gov/wctg/netanal/netanal-netmodels.html. Accessed 14 July 2011.
[16] Morton, D.P., Pan, F. and Saeger, K.J. Models for nuclear smuggling interdiction, IIE Transactions 38 (2007), 3–14
[17] Nandi, A.K. and Medal H.R. Methods for removing minimize the spread of infections, Comput. Oper. Res., 69 (2016), 10–24.
[18] Orlin, J. Max flows in O(nm) time, or better. STOC’13—Proceedings of the 2013 ACM Symposium on Theory of Computing, 765–774, ACM, New York, 2013.
[19] Pan, F. Stochastic network interdiction: Models and methods, Ph.D. thesis, University of Texas at Austin, 2005.
[20] Philips, C.A. The network inhibition problem, Proceeding of 25th ACM Symposium of Theory of Computing, San Diego, CA. (1993), 776–785.
[21] Salmeron, J. (2012), Deception tactics for network interdiction: A multi objective approach, Networks, 60(1), 45–58.
[22] Sullivan, K.M., Morton, D.P., Pan, F. and Smith, J.C. (2011), Securing a border under asymmetric information, Naval Res. Logist. 61(2) (2014), 91–100.
[23] Sullivan, K.M., Smith J.C. and Morton, D.P. Convex hull representation of the interdiction problem, Math. Program. 145(1-2) (2014), 349–376.
[24] Towle, E. and Luedtke, J. New solution approaches for the maximum reliability stochastic network interdiction problem, Comput. Manag. Sci. 15(3-4) (2018), 455–477.
[25] Wollmer, R.D. Removing arcs from a Network, Oper. Res. , 12 (1964), 934–940.
[26] Wood, R.K. Deterministic network interdiction problem, Math. Comp. Model., 17 (1993), 1–18
How to Cite
AfshariradM. (2020). Approximation algorithm for maximum flow network interdiction problem. Iranian Journal of Numerical Analysis and Optimization, 10(1), 1-18. https://doi.org/10.22067/ijnao.v10i1.75392
Research Article