A logarithmic approximation algorithm for the activation edge-multicover problem

Zeev Nutov, Avner Huri, Guy Kortsarz · Theoretical Computer Science · 2026

In the Activation Edge-Multicover problem we are given a multigraph 𝐺 = ( 𝑉 , 𝐸 ) with activation costs { 𝑐 𝑢 𝑒 , 𝑐 𝑣 𝑒 } for every edge 𝑒 = 𝑢 ⁢ 𝑣 ∈ 𝐸 , and degree requirements 𝑟 = { 𝑟 𝑣 : 𝑣 ∈ 𝑉 } . The goal is to find an edge subset J ⊆ E that minimizes the activation cost ∑ 𝑣 ∈ 𝑉 m a x ⁡ { 𝑐 𝑣 𝑢 ⁢ 𝑣 : 𝑢 ⁢ 𝑣 ∈ 𝐽 } , such that every v ∈ V has at least r v neighbors in the graph ( V, J ). Let 𝑘 = m a x 𝑣 ∈ 𝑉 ⁡ 𝑟 𝑣 be the maximum requirement and let 𝜃 = m a x 𝑒 = 𝑢 ⁢ 𝑣 ∈ 𝐸 ⁡ m a x ⁡ { 𝑐 𝑢 𝑒 , 𝑐 𝑣 𝑒 } m i n ⁡ { 𝑐 𝑢 𝑒 , 𝑐 𝑣 𝑒 } be the maximum quotient between the two costs of an edge. The case 𝜃 = 1 (when 𝑐 𝑢 𝑒 = 𝑐 𝑣 𝑒 for all 𝑒 = 𝑢 ⁢ 𝑣 ∈ 𝐸 ) is the well studied Min-Power Edge-Multicover problem, that admits approximation ratio O (log k ). On the other hand, for 𝑘 = 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 θ (cf. [2]), and no better approximation ratio was known. Our main result is the first (poly-)logarithmic approximation ratio 𝑂 ⁢ ( l o g ⁡ 𝑘 + l o g ⁡ m i n ⁡ { 𝜃 , 𝑛 } ) , that bridges between two known approximation ratios – O (log k ) for 𝜃 = 1 and O (log n ) for 𝑘 = 1 . This also implies approximation ratio 𝑂 ⁢ ( l o g ⁡ 𝑘 + l o g ⁡ m i 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. We also obtain the following improved approximation ratios for the Min-Power Edge-Multicover problem: (i) 𝑘 + 0 . 2 7 8 5 for general costs, improving the ratio of [3] for k ≤ 22. (ii) 1 + m a x 𝑥 ≥ 1 ⁡ l n ⁡ 𝑥 1 + 𝑥 / 𝜃 for unit costs, improving the ratio 2.16 [3] for k ≤ 10.

Read the paper · More papers on PaperTik