A Logarithmic Approximation Algorithm for the Activation Edge-Multicover Problem

doi:10.1007/978-3-032-09120-8_12

2026-01-01

PRE

Zeev Nutov *

Avner Huri

Guy Kortsarz

DOI：10.1007/978-3-032-09120-8_12

原文链接

原文求助

摘要

En 中文

在激活边-多重覆盖问题中，我们给定一个多重图G = (V, E)，每条边e = uv ∈ E具有激活成本{c(e)(u), c(e)(v)}，以及度要求r = {r(v) : v ∈ V}。目标是找到一个边子集J ⊆ E，使得激活成本Σ(v ∈ V) max{c(uv)(v) : uv ∈ J}最小化，同时确保每个v ∈ V在图(V, J)中至少有r(v)个邻居。设k = max(v ∈ V) r(v)为最大要求，设θ = max(e=uv ∈ E) max{c(e)(u), c(e)(v)}/min{c(e)(u), c(e)(v)}为一条边的两种成本的最大商。当θ = 1（即对所有e = uv ∈ E，c(e)(u) = c(e)(v)）时，这是已广泛研究的MIN-POWER EDGE-MULTICOVER问题，其近似比为O(log k)。另一方面，当k = 1时，该问题推广了FACILITY LOCATION问题，并具有紧近似比O(log n)。这表明对于一般的k和θ，近似比为O(k log n)（参见[28]），且未知的近似比更好。我们的主要结果是第一个（多项式）对数近似比O(log k + log min{θ, n})，它介于两个已知近似比之间——θ = 1时的O(log k)和k = 1时的O(log n)。这也表明ACTIVATION k-CONNECTED SUBGRAPH问题的近似比为O(log k + log min{θ, n}) + β(θ + 1)，其中β是该问题普通最小成本版本的已知最佳近似比。我们还获得了MIN-POWER EDGE-MULTICOVER问题的以下改进近似比：(i) 对于一般成本，k + 0.2785，改进了[8]中k ≤ 22时的近似比。(ii) 对于单位成本，1 + max(x ≥ 1) ln x/(1 + x/θ)，改进了[8]中k ≤ 10时的近似比2.16。

Keyword:

CONNECTIVITY

COVERS