Parametric Multiroute Flow and Its Application to Robust Network with k Edge Failures

摘要

In this work, we investigate properties of the function taking the real value h to the max h-route flow value, and apply the result to solve robust network flow problems. We show that the function is piecewise hyperbolic, and modify a parametric optimization technique, the ES algorithm, to find this function. The running time of the algorithm is O(λmn), when λ is a source-sink edge connectivity of our network, m is the number of links, and n is the number of nodes. We can use the result from that algorithm to solve two max-flow problems against k edge failures, referred to as max-MLA-robust flow and max-MLA-reliable flow. When h is optimally chosen from the function, we show that the max-h-route flow is an exact solution of both problems for graphs in a specific class. Our numerical experiments show that 98% of random graphs generated in the experiment are in that specific class. Given a parametric edge e, we also show that the function taking the capacity of e to the max-h-route flow value is linear piecewise. Hence we can apply our modified ES algorithm to find that function in O(h~2mn).