A 1.5-pproximation algorithms for activating 2 disjoint st-paths
share
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 ∈ E, a source-sink pair s,t ∈ V, and an integer k. The goal is to compute an edge set F ⊆ E of k internally node disjoint st-paths of minimum activation cost ∑_v ∈ Vmax_uv ∈ Ec_uv^v. The problem admits an easy 2-approximation algorithm. Alqahtani and Erlebach [CIAC, pages 1-12, 2013] claimed that Activation 2-DP admits a 1.5-approximation algorithm. Their proof 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.
READ FULL TEXT