An Approximation Algorithm for Stochastic Power Cover Problem

In this paper, we introduce the stochastic power cover (SPC) problem, which aims to determine the two-stage power assignment and minimize the total expected power consumption. For this problem, we are given a set U of n users, a set S of m sensors on the plane and k possible scenarios, where k is a polynomial and each consists of a probability of occurrence. Each sensor \(s\in S\) can adjust the power it produces by changing its radius and the relationship between them satisfies the following power equation \(p\left( s \right) =c\cdot r \left( s \right) ^{\alpha }\) . The objective is to identify the radius of each sensor in the first stage and augment the first-stage solution in order to cover all users and minimize the expected power over both stages. Our main result is to present an O( \(\alpha \) )-approximation algorithm by using the primal-dual technique.