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\in E$, and degree requirements $r=\{r_v:v\in V\}$. The goal is to find an edge subset $J\subseteq E$ of minimum activation cost ${\sum }_{v\in V}\max \{c_{uv}^v:uv\in J\}$,such that every $v\in V$ has at least $r_v$ neighbors in the graph $(V,J)$. Let $k={\max }_{v\in V}{r}_v$ be the maximum requirement and let $\theta ={\max }_{e=uv\in E}\frac{\max \{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 $\theta =1$ the problem admits approximation ratio $O(\log k)$. For $k=1$ it generalizes the Set Cover problem (when $\theta =\mathrm{\infty }$), and admits a tight approximation ratio $O(\log n)$. This implies approximation ratio $O(k\log n)$ for general $k$ and $\theta$, and no better approximation ratio was known. We obtain the first logarithmic approximation ratio $O(\log k+\log \min \{\theta ,n\})$, that bridges between the two known ratios – $O(\log k)$ for $\theta =1$ and $O(\log n)$ for $k=1$. This implies approximation ratio $O(\log k+\log \min \{\theta ,n\})+\beta \cdot (\theta +1)$ for the Activation $k$-Connected Subgraph problem, where $\beta$ is the best known approximation ratio for the ordinary min-cost version of the problem.