A 2√2k-approximation algorithm for minimum power k edge disjoint st-paths

In minimum power network design problems we are given an undirected graph G = (V, E) with edge costs {c(e) :e is an element of E}. The goal is to find an edge set F subset of E that satisfies S a prescribed property of minimum power p(c) (F) = Sigma(upsilon is an element of V) max{c(e) :e is an element of F is incident to upsilon}. In the MIN-POWER k EDGE DISJOINT st-PATHS problem F should contain k edge disjoint st-paths. The problem admits a k-approximation algorithm, and it was an open question to achieve an approximation ratio sublinear in k for simple graphs, even for unit costs. We give a 2 root 2k-approximation algorithm for general costs.