The continuous maximum capacity path interdiction problem
The continuous maximum capacity path interdiction problem
复制标题
连续最大容量路径阻断问题
DOI：
10.1016/j.ejor.2022.05.028
复制
发表时间：
2022
影响因子：
6.4
通讯作者：
Sefair, Jorge A.
中科院分区：
文献类型：
--
作者：
Tayyebi, Javad;Mitra, Ankan;Sefair, Jorge A.
研究了在一个容量受限的网络中，两个参与者（用户和阻断者）竞争的连续最大容量路径阻断问题。用户希望通过一条路径发送最大可能的流量，该路径的容量由其弧之间的最小容量给出。该算法利用牛顿法的离散形式，在多项式时间内解决了该问题。我们还证明了这个问题可以转化为一个零和博弈，它总是有一个纯纳什均衡点。我们证明了我们的算法在一组随机生成的网络的性能。
This paper studies the continuous maximum capacity path interdiction problem, where two players, user and interdictor, compete in a capacitated network. The user wants to send the maximum possible amount of flow through a path, whose capacity is given by the minimum capacity among its arcs. The budget-constrained interdictor decreases arc capacities by any continuous amount to reduce the quality of the user’s chosen path. We present an efficient algorithm based on a discrete version of the Newton’s method, which helps us solve the problem in polynomial time. We also prove that the problem can be transformed into a zero-sum game, which has always a pure Nash equilibrium point. We demonstrate the performance of our algorithm over a set of randomly generated networks.
登录
查看更多内容
影响因子：
6.4
作者：
Abraham P. Punnen
通讯作者：
Abraham P. Punnen
DOI：
10.1002/nav.3800170302
发表时间：
1970-01-01
期刊：
NAVAL RESEARCH LOGISTICS QUARTERLY
影响因子：
--
作者：
MCMASTERS, AW;MUSTIN, TM
通讯作者：
MUSTIN, TM
DOI：
10.1287/deca.2015.0325
发表时间：
2016
期刊：
Decis. Anal.
影响因子：
--
作者：
J. S. Borrero;O. Prokopyev;Denis Sauré
通讯作者：
Denis Sauré
针对突发对抗流量的自适应数据包路由
DOI：
10.1145/276698.276788
发表时间：
1998
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
W. Aiello;E. Kushilevitz;R. Ostrovsky;A. Rosén
通讯作者：
A. Rosén
DOI：
--
发表时间：
1996
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
G. Frederickson;Roberto Solis
通讯作者：
Roberto Solis