2022/08/19 by Nutov, Zeev
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2208.09373
In minimum power network design problems we are given an undirected graph G=(V,E) with edge costs \ce:e ∈ E\. The goal is to find an edge set F⊆ E that satisfies a prescribed property of minimum power pc(F)=∑v ∈ V max \ce: e ∈ F is incident to 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 2√(2k)-approximation algorithm for general costs.