An Approximation Algorithm for Multiroute Flow Decomposition

In this paper, we give an algorithm to optimize the number of elementary k-flows obtained by decomposing a given k-route flow. It is known that a k-route flow can be decomposed into a linear combination of elementary k-flows, and there are many algorithms proposed for that decomposition. However, the number of elementary k  -flows from those algorithms can be as large as O(|E|)O(|E|) when |E||E| is the number of edges in our network. As we have to reroute our flow for each elementary k-flow, it is more desirable to have a smaller number of the elementary flows in the combination. Let v be a maximum k-route flow value of our network, and h   be a real number such that 0