A 1.5-Approximation Algorithm for Activating Two Disjoint st-Paths
摘要
In the Activation k Disjoint st-Paths (Activation k-DP) problem we are given a graph \(G=(V,E)\) with activation costs \(\{c_{uv}^u,c_{uv}^v\}\) for every edge \(uv \in E\) , a source-sink pair \(s,t \in V\) , and an integer k. The goal is to compute an edge set \(F \subseteq E\) of k internally node disjoint st-paths of minimum activation cost \(\displaystyle \sum _{v \in V}\max _{uv \in F}c_{uv}^v\) . The problem admits an easy 2-approximation algorithm. Alqahtani & Erlebach [1] claimed that Activation 2-DP admits a 1.5-approximation algorithm. The proof in [1] has an error, and we will show that the approximation ratio of their algorithm is at least 2. We will then give a different algorithm with approximation ratio 1.5.