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\) that minimizes the 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 \(\displaystyle \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. The case \(\theta =1\) (when \(c_e^u=c_e^v\) for all \(e=uv \in E\) ) is the well studied Min-Power Edge-Multicover problem, that admits approximation ratio \(O(\log k)\) . On the other hand, for \(k=1\) the problem generalizes the Facility Location problem, and admits a tight approximation ratio \(O(\log n)\) . This implies approximation ratio \(O(k \log n)\) for general k and \(\theta \) (c.f. [28]), and no better approximation ratio was known. Our main result is the first (poly-)logarithmic approximation ratio \(O(\log k +\log \min \{\theta ,n\})\) , that bridges between two known approximation ratios – \(O(\log k)\) for \(\theta =1\) and \(O(\log n)\) for \(k=1\) . This also implies approximation ratio \(O\left( \log k +\log \min \{\theta ,n\}\right) +\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. We also obtain the following improved approximation ratios for the Min-Power Edge-Multicover problem: