A Logarithmic Approximation Algorithm for the Activation Edge-Multicover Problem

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 that minimizes the 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∈Vr_v be the maximum requirement and let θ=maxe=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. The case θ=1 (when c_e^u=c_e^v for all e=uv∈E) is the well studied Min-Power Edge-Multicover problem, that admits approximation ratio O(logk). On the other hand, for k=1 the problem generalizes the Facility Location problem, and admits a tight approximation ratio O(logn). This implies approximation ratio O(klogn) for general k and θ (c.f. [28]), and no better approximation ratio was known. Our main result is the first (poly-)logarithmic approximation ratio O(logk+logmin{θ,n}), that bridges between two known approximation ratios – O(logk) for θ=1 and O(logn) for k=1. This also implies approximation ratio Ologk+logmin{θ,n}+β·(θ+1) for the Activationk-Connected Subgraph problem, where β is the best known approximation ratio for the ordinary min-cost version of the problem. We also obtain the following improved approximation ratios for the Min-Power Edge-Multicover problem: k+0.2785 for general costs, improving the ratio of [8] for k≤22.1+maxx≥1lnx1+x/θ for unit costs, improving the ratio 2.16 [8] for k≤10. k+0.2785 for general costs, improving the ratio of [8] for k≤22. 1+maxx≥1lnx1+x/θ for unit costs, improving the ratio 2.16 [8] for k≤10.