An O(√(k))-approximation algorithm for minimum power k edge disjoint st -paths

08/19/2022

∙

by   Zeev Nutov, et al.

∙

0

∙

share

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 v}. In the Min-Power k Edge Disjoint st-Paths problem F should contains k edge disjoint st-paths. The problem admits a k-approximation algorithm, and it was an open question whether it admits approximation ratio sublinear in k even for unit costs. We give a 4√(2k)-approximation algorithm for general costs.