.png){kind=icon}
.png){kind=icon}
Return
Minimum st-cut interdiction problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cie.2020.106708.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper addresses a novel network interdiction problem, called the minimum st-cut interdiction problem. It is a Stackelberg game containing two players: one evader and one interdictor. The evader wants to choose a minimum st-cut in the network to cut any possible connection between two points s and t while the interdictor increases arc capacities under a budget constraint to make the minimum cut value as large as possible. In this paper, two classes of the problem are investigated: (1) the cost associated to any arc is proportional to the amount of its capacity increment; (2) the cost of any arc is fixed and independent from the amount of capacity changes. In the former, an algorithm is developed to solve the problem in polynomial time. In the latter, it is shown that the problem is strongly NP-hard and a Benders decomposition algorithm is proposed to solve the problem. Some experimental results on benchmarks and random data guarantee the correctness and performance of our proposed algorithms.
Keywords:
Network design
Network interdiction
Minimum cut
Benders decomposition
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6.5
Papers:
1.0W
Citations:
3.8W