On the power of randomization in network interdiction

被引：31
作者：
Bertsimas, Dimitris
Nasrabadi, Ebrahim [1 ]
Orlin, James B.
机构：
[1] MIT, Sloan Sch Management, Bldg E40-147, Cambridge, MA 02139 USA
来源：
OPERATIONS RESEARCH LETTERS | 2016年 / 44卷 / 01期
关键词：
Network flows; Interdiction; Game theory; Approximation;
D O I：
10.1016/j.orl.2015.11.005
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
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. (C) 2015 Elsevier B.V. All rights reserved.
引用
收藏
页码：114 / 120
页数：7
相关论文
共 23 条
  • [1] Ahuja RK, 1993, Network flows
  • [2] Maximizing residual flow under an arc destruction
    Aneja, YP
    Chandrasekaran, R
    Nair, KPK
    [J]. NETWORKS, 2001, 38 (04) : 194 - 198
  • [3] A NETWORK INTERDICTION MODEL FOR HOSPITAL INFECTION CONTROL
    ASSIMAKOPOULOS, N
    [J]. COMPUTERS IN BIOLOGY AND MEDICINE, 1987, 17 (06) : 413 - 422
  • [4] Shortest path network interdiction with asymmetric information
    Bayrak, Halil
    Bailey, Matthew D.
    [J]. NETWORKS, 2008, 52 (03) : 133 - 140
  • [5] Robust and Adaptive Network Flows
    Bertsimas, Dimitris
    Nasrabadi, Ebrahim
    Stiller, Sebastian
    [J]. OPERATIONS RESEARCH, 2013, 61 (05) : 1218 - 1242
  • [6] Bruch C., 2003, Network Interdiction and Stochastic Integer Programming, P51
  • [7] Stochastic network interdiction
    Cormican, KJ
    Morton, DP
    Wood, RK
    [J]. OPERATIONS RESEARCH, 1998, 46 (02) : 184 - 197
  • [8] The maximum residual flow problem:: NP-hardness with two-arc destruction
    Du, Donglei
    Chandrasekaran, R.
    [J]. NETWORKS, 2007, 50 (03) : 181 - 182
  • [9] Shortest-path network interdiction
    Israeli, E
    Wood, RK
    [J]. NETWORKS, 2002, 40 (02) : 97 - 111
  • [10] Reformulation and sampling to solve a stochastic network interdiction problem
    Janjarassuk, Udom
    Linderoth, Jeff
    [J]. NETWORKS, 2008, 52 (03) : 120 - 132
123