A (k + 1)-Approximation Robust Network Flow Algorithm and a Tighter Heuristic Method Using Iterative Multiroute Flow — Abstract
We consider two variants of a max-flow problem against $k$ edge failures, each of which can be both approximated by a multiroute flow algorithm. The maximum $k$-robust flow problem is to find the minimum max-flow value among $mchoose k$ networks that can be obtained by deleting each set of $k$ edges. The maximum $k$-balanced flow problem is to find a max-flow of the network such that the flow value is maximum against any set of $k$ edge failures, when deleting the corresponding flow to those $k$ edges in the original flow. We prove $C_M leqslant C_M',leqslant C_B leqslant C_R leqslant (k + 1)cdot C_M$, where $C_M$ is the max-$(k+1)$-route flow value, $C_M'$ is the effectiveness of the max-$(k+1)$-route flow after $k$ attacks, $C_B$ is the max-$k$-balanced flow value, and $C_R$ is the max-$k$-robust flow value. Also, we develop a polynomial-time heuristic algorithm for both cases, called the iterative multiroute flow. Our experimental results show that the average improvement made by our heuristic method can be up to $10%$ better than the multiroute flow algorithm. Compared to the optimal max-$k$-robust flow solutions -- obtained by a brute-force algorithm -- there is an average gap of $2%$ at most.