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 for every edge and degree requirements for every vertex. The goal is to find an edge subset J of minimum activation cost such that every vertex has at least its required number of neighbors in the graph. Let k be the maximum requirement and theta be the maximum quotient between the two costs of an edge. For theta equal to 1 the problem admits approximation ratio O(log k). For k equal to 1 it generalizes the Set Cover problem 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}), bridging the two known ratios O(log k) for theta equal to 1 and O(log n) for k equal to 1. This also implies an approximation ratio for the Activation k-Connected Subgraph problem based on the best known approximation ratio for the ordinary min-cost version of the problem.

Authors

• Zeev Nutov
• Avner Huri
• Guy Kortsarz

Keywords

No keywords are indexed for this paper.