A logarithmic approximation algorithm for the activation edge multicover problem
share
In the Activation Edge-Multicover problem we are given a multigraph G=(V,E) with activation costs {c_e^u,c_e^v} for every edge e=uv ∈ E, and degree requirements r={r_v:v ∈ V}. The goal is to find an edge subset J ⊆ E of minimum activation cost ∑_v ∈ Vmax{c_uv^v:uv ∈ J},such that every v ∈ V has at least r_v neighbors in the graph (V,J). Let k= max_v ∈ V r_v be the maximum requirement and let θ=max_e=uv ∈ Emax{c_e^u,c_e^v}/min{c_e^u,c_e^v} be the maximum quotient between the two costs of an edge. For θ=1 the problem admits approximation ratio O(log k). For k=1 it generalizes the Set Cover problem (when θ=∞), and admits a tight approximation ratio O(log n). This implies approximation ratio O(k log n) for general k and θ, and no better approximation ratio was known. We obtain the first logarithmic approximation ratio O(log k +logmin{θ,n}), that bridges between the two known ratios – O(log k) for θ=1 and O(log n) for k=1. This implies approximation ratio O(log k +logmin{θ,n}) +β· (θ+1) for the Activation k-Connected Subgraph problem, where β is the best known approximation ratio for the ordinary min-cost version of the problem.
READ FULL TEXT