Approximating Minimum Power Edge-Multi-Covers

Given a graph with edge costs, the

power

of a node is the maximum cost of an edge incident to it, and the power of a graph is the sum of the powers of its nodes. Motivated by applications in wireless networks, we consider the following fundamental problem in wireless network design. Given a graph

G

 = (

V

,

E

) with edge costs and degree bounds {

r

(

v

):

v

 ∈ 

V

}, the

Minimum-Power Edge-Multi-Cover

(

MPEMC

) problem is to find a minimum-power subgraph

J

of

G

such that the degree of every node

v

in

J

is at least

r

(

v

). Let

k

 =  max

v

 ∈ 

V

r

(

v

). For

k

 = Ω(log

n

), the previous best approximation ratio for

MPEMC

was

O

(log

n

), even for uniform costs [3]. Our main result improves this ratio to

O

(log

k

) for general costs, and to

O

(1) for uniform costs. This also implies ratios

O

(log

k

) for the

Minimum-Power

k

-Outconnected Subgraph

and

$O\left(\log k \log \frac{n}{n-k} \right)$

for the

Minimum-Power

k

-Connected Subgraph

problems; the latter is the currently best known ratio for the min-cost version of the problem. In addition, for small values of

k

, we improve the previously best ratio

k

 + 1 to

k

 + 1/2.