Parametric multiroute flow and its application to multilink-attack network
Parametric multiroute flow and its application to multilink-attack network
复制标题
参数化多路由流及其在多链路攻击网络中的应用
DOI：
10.1016/j.disopt.2016.05.002
复制
发表时间：
2016
影响因子：
1.1
通讯作者：
Hidefumi Hiraishi and Hiroshi Imai
中科院分区：
文献类型：
--
作者：
Jean-Francois Baffier;Vorapong Suppakitpaisarn;Hidefumi Hiraishi and Hiroshi Imai
我们研究了k次攻击下网络中最大流问题的变种。网络阻断问题是在(m，k)个网络中通过删除每组k条链路而得到的最小最大流量值。自适应网络流问题是当删除到原始流中的那k个链路的对应流时，找到网络的流，使得流值对于任何k个链路集的攻击是最大的。首先，我们证明了最大-(k+1)-路由流对这两个问题都是(k+1)-近似。此外，我们还为这两种情况开发了一种多项式时间启发式算法，称为迭代多路由流。然后在第二阶段，我们研究了取实值h到最大h路流量值的函数的性质，并将结果应用于解决这两个问题。我们证明了该函数是分段双曲的，并对标准的参数优化技术进行了修改以求出该函数。该算法的运行时间为O(λT)，其中λ是网络的源宿边连通性，T是最大流算法的计算时间。我们证明了在某些情况下，当h被最优选择时，最大-h-路由流是这两个问题的精确解。
We investigate variants of the max-flow problem in a network under k attacks. The network interdiction problem is to find the minimum max-flow value among (m k) networks that can be obtained by deleting each set of k links. The adaptive network flow problem is to find a flow of the network such that the flow value is maximum against any set of k links attack, when deleting the corresponding flow to those k links in the original flow. First, we prove that max-(k+ 1)-route flow is a (k+ 1)-approximation for both problems. Also, we develop a polynomial-time heuristic algorithm for both cases, called the iterative multiroute flow. Then in a second phase, we investigate properties of the function taking the real value h to the max h-route flow value, and apply the result to solve both of the problems. We show that the function is piecewise hyperbolic, and modify a standard parametric optimization technique to find this function. The running time of the algorithm is O (λ T), when λ is a source–sink edge connectivity of our network and T the computation time of a max-flow algorithm. We show that for some instances, when h is optimally chosen, the max-h-route flow is an exact solution for both problems.
登录
查看更多内容
稳健且自适应的网络流
DOI：
10.1287/opre.2013.1200
发表时间：
2013
期刊：
Oper. Res.
影响因子：
--
作者：
D. Bertsimas;E. Nasrabadi;S. Stiller
通讯作者：
S. Stiller
线性和分段线性成本函数的参数查询优化
DOI：
10.1016/b978-155860869-6/50023-8
发表时间：
2002
期刊：
--
影响因子：
--
作者：
Arvind Hulgeri;S. Sudarshan
通讯作者：
S. Sudarshan
一种获取网络中最大δ-可靠流的方法
DOI：
--
发表时间：
1998
期刊：
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
影响因子：
--
作者：
W. Kishimoto;M. Takeuchi
通讯作者：
M. Takeuchi
大型共享数据库中有效记录分割的数学技术
DOI：
--
发表时间：
1976
期刊：
JACM
影响因子：
--
作者：
M. Eisner;D. Severance
通讯作者：
D. Severance
不同容量对所有对 2 路由网络流量的影响
DOI：
10.1016/j.endm.2009.11.011
发表时间：
2009
期刊：
Electron. Notes Discret. Math.
影响因子：
--
作者：
Madiagne Diallo;Serigne Gueye;P. Berthomé
通讯作者：
P. Berthomé