Balanced paths in telecommunication networks: some computational results

Given a weighted directed network G, we consider the problem of computing k balanced paths from given source nodes to given destination nodes of G, i.e. k paths such that the difference in cost between the longest and the shortest path is minimized. For the special case in which G is an acyclic network, the balanced path problem is solvable in pseudo-polynomial time. On the contrary, when arc-disjoint or node-disjoint balanced paths are looked for, the problem is strongly NP-Hard. In this work we examine the balanced path problem in this more general setting, focusing on telecommunication applications