On the power of randomization in network interdiction
Author(s)
Bertsimas, Dimitris J; Nasrabadi, Ebrahim; Orlin, James B
DownloadOrlin_On the power of Randomization.pdf (128.0Kb)
PUBLISHER_CC
Publisher with Creative Commons License
Creative Commons Attribution
Terms of use
Metadata
Show full item recordAbstract
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. Keywords
Network flows
Interdiction
Game theory
Approximation
Date issued
2015-12Department
Sloan School of ManagementJournal
Operations Research Letters
Publisher
Elsevier
Citation
Bertsimas, Dimitris et al. “On the Power of Randomization in Network Interdiction.” Operations Research Letters 44, 1 (January 2016): 114–120 © 2015 Elsevier B.V.
Version: Author's final manuscript
ISSN
0167-6377