A 22k-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∈E}. The goal is to find an edge set F⊆E that satisfies a prescribed property of minimum power p_c(F)=∑_v∈Vmax⁡{c_e:e∈F is incident to v}. 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 22k-approximation algorithm for general costs.