2023/08/05 by Nutov, Zeev
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2308.02901
In the Activation Edge-Multicover problem we are given a multigraph G=(V,E) with activation costs \ceu,cev\ for every edge e=uv ∈ E, and degree requirements r=\rv:v ∈ V\. The goal is to find an edge subset J ⊆ E of minimum activation cost ∑v ∈ Vmax\cuvv:uv ∈ J\,such that every v ∈ V has at least rv neighbors in the graph (V,J). Let k= maxv ∈ V rv be the maximum requirement and let θ=maxe=uv ∈ E \fracmax\ceu,cev\min\ceu,cev\ 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.