.png){kind=icon}
.png){kind=icon}
Return
A Logarithmic Approximation Algorithm for the Activation Edge-Multicover Problem
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-032-09120-8_12.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 is an element of E, and degree requirements r = {r(v) : v is an element of V}. The goal is to find an edge subset J subset of E that minimizes the activation cost Sigma(v is an element of V) max{c(uv)(v) : uv is an element of J}, such that every v is an element of V has at least r(v) neighbors in the graph (V, J). Let k = max(v is an element of V) r(v) be the maximum requirement and let theta = max(e=uv is an element of E) 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 is an element of 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(log k + log min{theta, n})+beta.(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: (i) k + 0.2785 for general costs, improving the ratio of [8] for k <= 22. (ii) 1+max(x >= 1) ln x/1 + x/theta for unit costs, improving the ratio 2.16 [8] for k <= 10.
Keywords:
CONNECTIVITY
COVERS
Journal
A
IF:
0
Papers:
13
Citations:
0