A note on the minimum power partial cover problem on the plane

Abstract

Given a set of n points and a set of m sensors on the plane, each sensor s can adjust its power p(s) and the covering range which is a disk of radius r(s) satisfying $p(s)=c\cdot r(s)^{\alpha }$. The minimum power partial cover problem, introduced by Freund (Proceedings of international workshop on approximation and online algorithms, pp 137–150. 2011. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.737.1320), is to determine the power assignment on every sensor such that at least k ($k\le n$) points are covered and the total power consumption is minimized. By generalizing the method in Li (Journal of Com. Opti.2020. https://doi.org/10.1007/s10878-020-00567-3) whose approximation ratio is $3^{\alpha }$ and enlarging the radius of each disk in the relaxed independent set, we present an $O(\alpha )$-approximation algorithm.

1 Introduction

Motivated by the purpose of saving energy while keeping an acceptable quality of service, Freund and Rawitz (2003) introduced the minimum power partial cover (MinPPC) problem, which is defined as follows. Given a set X of n points, a set S of m sensors on the plane and an integer k satisfying $0\le k\le n$, each sensor s can adjust its power and the covering range of s with power p(s) is a disk of radius r(s) satisfying

$$\begin{aligned} p(s)=c\cdot r(s)^{\alpha }, \end{aligned}$$

(1)

where the coefficient c and the attenuation factor $\alpha \ge 1$ are some constants. A point $x\in X$ is covered by a sensor $s\in S$ with power p(s) if x belongs to the disk supported by p(s), that is $x\in Disk(s,r(s))$, where Disk(s, r(s)) is the disk centered at s whose radius r(s) is determined by (1). A point is covered by a power assignment $p: S\mapsto {\mathbb {R}^+}$ if it belongs to some disk supported by p. The MinPPC problem (Freund and Rawitz 2003; Li et al. 2020) is to find a power assignment p covering at least k points such that the total power $\sum _{s\in S}p(s)$ is as small as possible. Here, we assume that there is no limit on the power at a sensor.

By means of the generic reduction of partial covering to prize collecting covering in konemann et al. (2011), Freund and Rawitz (2003) designed a ($12+\epsilon$)-approximation algorithm for the MinPPC problem with $\alpha =2$, where $\epsilon$ is an arbitrary constant greater than zero. Li et al. (2020) presented a primal-dual algorithm for the MinPPC problem with approximation ratio at most $3^{\alpha }$. Most recently, Ran et al. (2021) presented a polynomial time approximation scheme with running time $O(\frac{1}{\epsilon }(mn)^{O(1/\epsilon ^{\alpha +4})})$.

The MinPPC problem is a special case of the minimum power partial multi-cover problem (Liang et al. 2021), which is to find an assignment of powers to sensors such that at least a required number of points are covered up to their covering requirements. If all the points and sensors are on a line, Liang et al. (2021) presented an optimal algorithm based on dynamic programming when the maximum covering requirement of points is upper bounded by a constant.

Although there exists a polynomial time approximation scheme for the MinPPC problem (Ran et al. 2021), the running time is quite time-consuming. In this paper, through in-depth analysis of geometric properties, we generalize the method in Li et al. (2020) and design a combinatorial polynomial-time algorithm for the MinPPC problem, where we introduce a novel notion, called relaxed independent set, which maybe found other applications in related geometric problems.

2 Previous algorithm

As mentioned in Li et al. (2020), at most mn disks need to be considered. We denote the set of such disks by $\mathcal{D}$. In the following, denote by $(X,\mathcal{D},k)$ an instance of the MinPPC problem, and use $OPT(X,\mathcal{D},k)$ to denote the optimal power for instance $(X,\mathcal{D},k)$. For each disk $D\in \mathcal{D}$, use $X(D)=X\cap D$ to represent the set of points covered by D, r(D) to represent the radius of disk D, p(D) to represent the the power of disk D, and s(D) to represent the center of disk D. Correspondingly, for a set of disks $\mathcal{D}'\subseteq \mathcal{D}$, we use $X(\mathcal{D}')=\bigcup _{D\in \mathcal{D}'}X(D)$ to denote the set of points covered by the union of disks in $\mathcal{D}'$.

As mentioned in Li et al. (2020), in order to control the approximation ratio, we need to guess the maximum radius of a disk in an optimal solution. Suppose $D_{\max }\in \mathcal{D}$ is the guessed disk. For simplicity of notation, use $(X,\mathcal{D}, k)$ to denote the residual instance after the guessing, assuming that X does not contain the points covered by $D_{\max }$ and every disk in $\mathcal{D}$ has radius at most $r(D_{\max })$. For each disk $D\in \mathcal{D}$, introduce a variable $z_{D}\in \{0,1\}$ indicating whether disk D is picked, that is, $z_{D}=1$ if and only if D is picked. For each point $x\in X$, introduce a variable $y_{x}\in \{0,1\}$ indicating whether point x is covered, that is, $y_{x}=0$ if and only if x is covered. The MinPPC problem can be formulated as the following integer linear program (ILP):

$$\begin{aligned}&~&\min \sum _{D:D\in {\mathscr {D}}}c\cdot r(D)^\alpha \cdot z_D\nonumber \\ { s.t.}&~&\sum _{D:x\in D} z_{D}+y_{x} \ge 1, ~ \forall x\in X \nonumber \\&~&\sum _{x: x\in X}y_{x}\le n-k,\nonumber \\&~&z_{D}\in \{0,1\},~\forall D\in {\mathscr {D}},\nonumber \\&~&y_{x}\in \{0,1\},~\forall x\in X. \end{aligned}$$

(2)

The dual program of the LP-relaxation of ILP (2) is:

$$\begin{aligned}&~&\max \sum _{x:x\in X}\beta _x-(n-k)\gamma \nonumber \\ { s.t.}&~&\sum _{x: x\in D} \beta _{x} \le c\cdot r(D)^\alpha , ~ \forall D\in \mathscr {D} ,\nonumber \\&~&0\le \beta _{x}\le \gamma ,~ \forall x\in X,\nonumber \\&~&\gamma \ge 0. \end{aligned}$$

(3)

The approximation algorithm proposed in Li et al. (2020) consists of three steps:

(i) In the first step, a primal dual method is employed to find a dual feasible solution $(\beta ,\gamma )$ and a primal feasible solution $\mathcal{D}_{tight}\subseteq \mathcal{D}$ of tight disks covering at least k points, where we say that a disk $D\in \mathcal{D}$ is tight if

$$\begin{aligned} \sum _{x\in D}\beta _x=c\cdot r(D)^{\alpha }. \end{aligned}$$

(ii) Before going into the second step, remove the disk $D_{rmv}$ which is the last disk added into $\mathcal{D}_{tight}$. Then, in the second step, a maximal independent set of disks $\mathcal{I} \subseteq \mathcal{D}_{tight} \setminus \{D_{rmv}\}$ is computed in a greedy manner, that is, disks in $\mathcal{I}$ are mutually disjoint, while any disk $D\in \mathcal{D}_{tight} \setminus \{D_{rmv}\}$ which is not picked into $\mathcal{I}$ intersects some disk in $\mathcal{I}$.

(iii) In the third step, every disk in $\mathcal{I}$ has its radius enlarged three times. Such set of disks together with $D_{rmv}$ are the output of the algorithm.

The approximation ratio $3^{\alpha }$ of this algorithm is caused by enlarging three times of the radius of the disks in $\mathcal{I}$, as the disks in $\mathcal{I}$ are “far” from each other. In this paper, replacing “independent set” by “relaxed independent set” where the disks are not “far” from each other, we design an improved approximation algorithm with approximation ratio $O(\alpha )$.

3 $\rho$-relaxed independent set

In this section, we introduce the definition and some geometric properties of $\rho$-relaxed independent set, where $\rho \in [0,2]$ is a given constant. Given a set X of points and a set $\mathcal{D}'$ of disks on the plane, for any two disks $D_1,D_2\in \mathcal{D}'$, if $X(D_{1})\cap X(D_{2})=\emptyset$ or

$$\begin{aligned} d(s(D_1), s(D_2))> \rho \max \{r(D_1), r(D_2)\}, \end{aligned}$$

(4)

we call that $\mathcal{D}'$ is a $\rho$-relaxed independent set, where d(a, b) is the Euclidean distance between points a and b. If $\rho =2$, we have $d(s(D_1), s(D_2))> 2 \max \{r(D_1), r(D_2)\}\ge r(D_1)+r(D_2)$ for any two disks $D_1,D_2\in \mathcal{D}'$, implying that the disks in $\mathcal{D}'$ are mutually disjoint. Therefore, $\rho$-relaxed independent set is a generalization of independent set defined in Li et al. (2020). In Fig. 1, the set of disks in (a) is not a $\rho$-relaxed independent set, and the set of disks in (b) is a $\rho$-relaxed independent set, where $\rho =1$.

Fig. 1

(a) is not 1-relaxed independent set; (b) is 1-relaxed independent set

Lemma 1

For any $t\in \{ 2,3,4,\ldots \}$,we have$\max _{x\in X}|\{D|x\in D \in \mathcal{D}'\}|\le t-1$, where $\mathcal{D}'$ is a $\rho$-relaxed independent set with $\rho =2\sin \frac{\pi }{t}$.

Proof

If there is a point $x\in X$ such that $|\{D|x\in D \in \mathcal{D'}\}|>t-1$, we choose any t disks $D_i$ with $s(D_i)=s_i$ covering x, where $i=1,2,\ldots ,t$, and assume that the angular position relationship between $s_i$ and x is shown in Fig. 2a. Since $\sum _{i=1}^t \angle i=2\pi$, there exist two disks $D_{i_1}$ and $D_{i_2}$ such that the angle between two line segments $xs_{i_1}$ and $xs_{i_2}$ is no more than $\frac{2\pi }{t}$ (see Fig. 2b), i.e.,

$$\begin{aligned} \angle s_{i_1}xs_{i_2}\le \frac{2\pi }{t}. \end{aligned}$$

(5)

Without loss of generality, assume that $d(s_{i_1},x)\ge d(s_{i_2},x)$. By the sine theorem, we have

$$\begin{aligned} \angle xs_{i_2}s_{i_1} \ge \frac{1}{2}(\pi -\angle s_{i_1}xs_{i_2})\ge \angle xs_{i_1}s_{i_2} \end{aligned}$$

(6)

and

$$\begin{aligned} \frac{d(s_{i_1},s_{i_2})}{\sin \angle s_{i_1}xs_{i_2}}=\frac{d(s_{i_1},x)}{\sin \angle xs_{i_2}s_{i_1}}. \end{aligned}$$

Therefore,

$$\begin{aligned} d(s_{i_1},s_{i_2})= & {} \frac{\sin \angle s_{i_1}xs_{i_2}}{\sin \angle xs_{i_2}s_{i_1}}d(s_{i_1},x)\\\le & {} \frac{\sin \angle s_{i_1}xs_{i_2}}{\sin \frac{1}{2}(\pi -\angle s_{i_1}xs_{i_2})}d(s_{i_1},x)\\= & {} \frac{2\sin \frac{1}{2}\angle s_{i_1}xs_{i_2}\cos \frac{1}{2}\angle s_{i_1}xs_{i_2}}{\cos \frac{1}{2}\angle s_{i_1}xs_{i_2}}d(s_{i_1},x)\\\le & {} 2\sin \frac{\pi }{t} d(s_{i_1},x)\\\le & {} 2\sin \frac{\pi }{t} r(D_{i_1})\\\le & {} 2\sin \frac{\pi }{t} \max \{r(D_{i_1}),r(D_{i_2})\}, \end{aligned}$$

where the first inequality follows from (6), and the second inequality follow from (5). It contradicts the definition of $\rho$-relaxed independent set $\mathcal{D'}$ with $\rho =2\sin \frac{\pi }{t}$. Therefore, the theorem holds. $\square$

Fig. 2

(a) is the position of $s_1$,..., $s_t$ and x; (b) is the relative positions of vertices x, $s_{i_1}$, $s_{i_2}$

4 Our algorithm

We use the primal-dual method in Li et al. (2020) to find a feasible solution $\mathcal{D}_{tight}\subseteq \mathcal{D}$ which covers at least k points. Before going into the second step, remove the disk $D_{rmv}$ which is the last disk added into $\mathcal{D}_{tight}$. Then, a maximal $\rho$-relaxed independent set of disks $\mathcal{I} \subseteq \mathcal{D}_{tight} \setminus \{D_{rmv}\}$ is computed in a greedy manner. Finally, every disk in $\mathcal{I}$ has its radius enlarged $1+\rho$ times. Such set of disks together with $D_{rmv}$ are the output of the algorithm. For each integer $t\in \{2,3,4,\ldots \}$, our approximation algorithm is described in Algorithm 1.

Lemma 2

$\mathcal{D}_f$ is a feasible solution.

Proof

$\mathcal{D}_f$ can be represented as

$$\begin{aligned} \mathcal{D}_f=\{Disk(s(D), (1+\rho )r(D))|D\in \mathcal{I}\}\cup \{D_{rmv}\}. \end{aligned}$$

(7)

For any point $x\in X(\mathcal{D}_{tight})$, if x is covered by $\mathcal{I}\cup \{D_{rmv}\}$, x must be covered by $\mathcal{D}_f$. Consider any point x which is covered by a disk $D_{l'}\in \mathcal{D}_{tight}\setminus (\mathcal{I}\cup \{D_{rmv}\})$. Following from the definition of $\rho$-relaxed independent set, there is a disk $D_{l''} \in \mathcal{I}$ satisfying that $r(D_{l''})\ge r(D_{l'})$ and $d(s(D_{l''}), s(D_{l'}))\le \rho r(D_{l''})$. Therefore, we have

$$\begin{aligned} d(x, s(D_{l''}))\le & {} d(x, s(D_{l'}))+d(s(D_{l'}), s(D_{l''}))\\\le & {} r(D_{l'})+d(s(D_{l'}), s(D_{l''}))\\\le & {} (1+\rho ) r(D_{l''}). \end{aligned}$$

It implies that x is cover by the disk $Disk(s(D_{l''}), (1+\rho )r(D_{l''}))\in \mathcal{D}_f$. Therefore, any point x covered by $\mathcal{D}_{tight}$ is also covered by $\mathcal{D}_f$ and $|X(\mathcal{D}_f)|\ge |X(\mathcal{D}_{tight})|>k$, implying that $\mathcal{D}_f$ is a feasible solution. $\square$

Lemma 3

For any integer $t\in \{2,3,4,\ldots \}$, the objective value of $\mathcal{D}_f$ is no more than $(t-1)(1+2\sin \frac{\pi }{t})^\alpha OPT(X, \mathcal{D}, k)+p(D_{rmv})$.

Proof

By the choice of Algorithm 1, for each disk $D\in \mathcal{I}\subseteq \mathcal{D}_{tight}$, we have $\sum _{x:x\in D}\beta _x=c\cdot r(D)^\alpha$. As in the proof of Lemma 3.1 in Li et al. (2020), we have

$$\begin{aligned} p(\mathcal{I})= & {} \sum _{D: D\in \mathcal{I}}c\cdot r(D)^\alpha \\= & {} \sum _{D:D\in \mathcal{I}}\sum _{x:x\in D}\beta _x \\= & {} \sum _{x:x\in X(\mathcal{I})}\beta _x|\{D|x\in D \in \mathcal{I}\}| \\\le & {} (t-1)\cdot \sum _{x:x\in X(\mathcal{I})}\beta _x \\\le & {} (t-1)\cdot \sum _{x:x\in X(\mathcal{D}_{tight}\setminus \{D_{rmv}\})}\beta _x \\= & {} (t-1)\left( \sum _{x:x\in X}\beta _x-\sum _{x:x\in X\setminus X(\mathcal{D}_{tight}\setminus \{D_{rmv}\})}\beta _x\right) , \\\le & {} (t-1)\cdot \left( \sum _{x: x\in X}\beta _x-(n-k)\gamma \right) \\\le & {} (t-1)\cdot OPT(X, \mathcal{D}, k). \end{aligned}$$

where the first inequality follows from Lemma 1, and the second inequality follows from that $\mathcal{I}\subseteq \mathcal{D}_{tight}\setminus \{D_{rmv}\}$.

Since every disk in $\mathcal{I}$ has its radius enlarged $1+\rho$ times where $\rho =2\sin \frac{\pi }{t}$, we have

$$\begin{aligned} p(\mathcal{D}_f)= & {} \sum _{D:D\in \mathcal{D}_f}c\cdot r(D)^\alpha \\= & {} \left( 1+2\sin \frac{\pi }{t}\right) ^\alpha p(\mathcal{I})+p(D_{rmv})\\\le & {} (t-1)\cdot \left( 1+2\sin \frac{\pi }{t}\right) ^\alpha \cdot OPT(X, \mathcal{D}, k)+p(D_{rmv}). \end{aligned}$$

Thus, the lemma holds. $\square$

By using the similar discussion as in (subsection 3.2, Li et al. 2020), we obtain

Theorem 1

For any integer $t\in \{2,3,4,\ldots \}$, there is a $(t-1)(1+2\sin \frac{\pi }{t})^\alpha$-approximation algorithm for the MinPPC problem, which runs in time $O(kn^2m^2)$.

When $t=2$, our algorithm is exactly the algorithm in Li et al. (2020), and the approximation ratio is $3^\alpha$. For different values of t and $\alpha$, the approximation ratio is depicted in Fig. 3.

For each given value of $\alpha$, let $f(t)=(t-1)(2\sin \frac{\pi }{t}+1)^\alpha$. Since

$$\begin{aligned} \lim _{\alpha \rightarrow +\infty } \frac{f\left( \lfloor \alpha \rfloor \right) }{\alpha }=\lim _{\alpha \rightarrow +\infty } \frac{\lfloor \alpha \rfloor -1}{\alpha } \left( 2\sin \frac{\pi }{\lfloor \alpha \rfloor }+1\right) ^{\lfloor \alpha \rfloor \cdot \frac{\alpha }{\lfloor \alpha \rfloor }}=e^{2\pi }, \end{aligned}$$

f(t) is nearly linear in the value of $\alpha$ when $\alpha$ is large enough, which can also be verified in Fig. 3. The best value of t, denoted by $t^*=\arg \min _{t\in \{2,3,4,\ldots \}}(t-1)(1+2\sin \frac{\pi }{t})^\alpha$, for different value of $\alpha$ is depicted in Fig. 4.

For each given value of $\alpha$, set $t^*=\arg \min _{t\in \{2,3,4,\ldots \}}(t-1)(1+2\sin \frac{\pi }{t})^\alpha$. The approximation of Algorithm 1: MinPPC($t^*$) is

$$\begin{aligned} (t^*-1)(1+2\sin \frac{\pi }{t^*})^\alpha \approx e^{2\pi }\alpha =O(\alpha ), \end{aligned}$$

when $\alpha$ is large enough. The comparison of our approximation ratio and $3^{\alpha }$ in (Li et al. (2020)) is depicted in Fig. 5.

Fig. 3

The approximation ratio dependent on the values of t and $\alpha$

Fig. 4

The best value of t dependent on the value of $\alpha$

Fig. 5

The comparison of two approximation ratios

5 Conclusion

We generalize the method in Li et al. (2020) and obtain an improved approximation algorithm for the minimum power partial cover problem. The relaxed independent set introduced in this paper may have independent interesting in related area.