Approximation algorithm for maximum flow network interdiction problem

Document Type : Research Article

Author

• M. Afsharirad

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

10.22067/ijnao.v10i1.75392

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

20.1001.1.24236977.2020.10.1.1.1

---

References

[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