On the power of randomization in network interdiction. (English) Zbl 1408.91038
Summary: In this paper, we introduce the randomized network interdiction problem that allows the interdictor to use randomness to select arcs to be removed. We model the problem in two different ways: arc-based and path-based formulations, depending on whether flows are defined on arcs or paths, respectively. We present insights into the modeling power, complexity, and approximability of both formulations.
MSC:
| 91A43 | Games involving graphs |
| 90B10 | Deterministic network models in operations research |
| 90C35 | Programming involving graphs or networks |
References:
| [1] | Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network flows. theory, algorithms, and applications, (1993), Prentice Hall Englewood Cliffs, NJ · Zbl 1201.90001 |
| [2] | Aneja, Y. P.; Chandrasekaran, R.; Nair, K. P.K., Maximizing residual flow under arc destruction, Networks, 34, 194-198, (2001) · Zbl 0993.90014 |
| [3] | Assimakopoulos, N., A network interdiction model for hospital infection control, Comput. Biol. Med., 17, 6, 413-422, (1987) |
| [4] | Bayrak, H.; Bailey, M. D., Shortest path network interdiction with asymmetric information, Networks, 52, 3, 133-140, (2008) · Zbl 1171.90345 |
| [5] | Bertsimas, D.; Nasrabadi, E.; Stiller, S., Robust and adaptive network flows, Oper. Res., 61, 5, 1218-1242, (2013) · Zbl 1291.90046 |
| [6] | Burch, C.; Carr, R.; Krumke, S.; Marathe, M.; Phillips, C.; Sundberg, E., A decomposition-based pseudoapproximation algorithm for network flow inhibition, (Network Interdiction and Stochastic Integer Programming, (2003), Springer), 51-68 · Zbl 1051.90005 |
| [7] | Cormican, K. J.; Morton, D. P.; Wood, R. K., Stochastic network interdiction, Oper. Res., 46, 2, 184-197, (1998) · Zbl 0987.90516 |
| [8] | Du, D.; Chandrasekaran, R., The maximum residual flow problem: NP-hardness with two-arc destruction, Networks, 50, 181-182, (2007) · Zbl 1146.90345 |
| [9] | Israeli, E.; Wood, R. K., Shortest-path network interdiction, Networks, 40, 2, 97-111, (2002) · Zbl 1027.90106 |
| [10] | Janjarassuk, U.; Linderoth, J., Reformulation and sampling to solve a stochastic network interdiction problem, Networks, 52, 3, 120-132, (2008) · Zbl 1173.90345 |
| [11] | Lim, C.; Smith, J. C., Algorithms for discrete and continuous multicommodity flow network interdiction problems, IIE Trans., 39, 15-26, (2007) |
| [12] | J. Matuschke, T. McCormick, G. Oriolo, B. Peis, M. Skutella, October 2015. Personal communication. |
| [13] | Murray, A.; Matisziw, T.; Grubesic, T., Critical network infrastructure analysis: interdiction and system flow, J. Geogr. Syst., 9, 2, 103-117, (2007) |
| [14] | C.A. Phillips, The network inhibition problem, in: Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, San Diego, CA, 1993, pp. 776-785. · Zbl 1310.90018 |
| [15] | Ratliff, H. D.; Sicilia, G. T.; Lubore, S. H., Finding the \(n\) most vital links in flow networks, Manage. Sci., 21, 5, 531-539, (1975) · Zbl 0311.90073 |
| [16] | Rocco S., C. M.; Ramirez-Marquez, J. E., A bi-objective approach for shortest-path network interdiction, Comput. Ind. Eng., 59, 2, 232-240, (2010) |
| [17] | Royset, J. O.; Wood, R. K., Solving the bi-objective maximum-flow network-interdiction problem, INFORMS J. Comput., 19, 175-184, (2007) · Zbl 1241.90139 |
| [18] | Salmeron, J.; Wood, K.; Baldick, R., Analysis of electric grid security under terrorist threat, IEEE Trans. Power Syst., 19, 2, 905-912, (2004) |
| [19] | R.L. Steinrauf, Network interdiction models, (Master’s thesis), Monterey, CA, 1991. |
| [20] | Wald, A., Statistical decision functions which minimize the maximum risk, Ann. Math., 46, 46-58, (1945) |
| [21] | Whiteman, P. S., Improving single strike effectiveness for network interdiction, Mil. Oper. Res., 4, 15-30, (1999) |
| [22] | Wollmer, R., Removing arcs from a network, Transp. Res. B, 12, 934-940, (1964) · Zbl 0204.20102 |
| [23] | Wood, R. K., Deterministic network interdiction, Math. Comput. Modelling, 17, 1-18, (1993) · Zbl 0800.90772 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
