On the power of randomization in network interdiction

详细信息    查看全文

• 作者：Dimitris Bertsimas ^{dbertsim@mit.edu" class="auth_mail" title="E-mail the corresponding author} ; Ebrahim Nasrabadi ; ^{enasrabadi58@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; James B. Orlin ^{jorlin@mit.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Network flows ; Interdiction ; Game theory ; Approximation
• 刊名：Operations Research Letters
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：44
• 期：1
• 页码：114-120
• 全文大小：438 K

文摘

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.