Search

In this paper, we consider the $ k $-prize-collecting minimum power cover problem ($ k $-PCPC), which is defined as follows. Given a set $ X = \{x_1, x_2, $ $ \cdots, x_n\} $ of $ n $ points and a set $ S = \{s_1, s_2, \cdots, s_m\} $ of $ m $ sensors on the plane $ \mathbb{R}^2 $, an integer $ k $ satisfying $ 0 \leq k \leq n $ and a penalty function $ \pi: X \rightarrow \mathbb{R}_0^{+} $, each sensor $ s\in 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 $, where $ \alpha\geq 1 $ and $ c>0 $ are constants. We are asked to determine a set of disks $ \mathcal{F} $ such that at least $ k $ points are covered, where the center of any disk in $ \mathcal{F} $ is a sensor. The objective is to minimize the total power of the set of disks $ \mathcal{F} $ plus the penalty of $ R $, where $ R $ is the set of points that are not covered by $ \mathcal{F} $. It has been proven that this problem is NP-hard and admits a $ 3^\alpha $-approximation algorithm. By using some properties of relaxed independent sets and combining the guessing technique and the primal-dual method, we design an $ O(\alpha) $-approximation algorithm. Numerical experiments are tested to evaluate the performance of the $ 3^\alpha $-approximation algorithm and our new algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we consider parallel-machine scheduling with release times and submodular penalties ( P | r j , r e j e c t | C max + π (R) ), in which each job can be accepted and processed on one of m identical parallel machines or rejected, but a penalty must paid if a job is rejected. Each job has a release time and a processing time, and the job can not be processed before its release time. The objective of P | r j , r e j e c t | C max + π (R) is to minimize the makespan of the accepted jobs plus the penalty of the rejected jobs, where the penalty is determined by a submodular function. This problem generalizes a multiprocessor scheduling problem with rejection, the parallel-machine scheduling with submodular penalties, and the single machine scheduling problem with release dates and submodular rejection penalties. In this paper, inspired by the primal-dual method, we present a combinatorial 2-approximation algorithm to P | r j , r e j e c t | C max + π (R) . This ratio coincides with the best known ratio for the parallel-machine scheduling with submodular penalties and the single machine scheduling problem with release dates and submodular rejection penalties. [ABSTRACT FROM AUTHOR]