The Online Power Cover Problem on a Line
摘要
In this paper, we study the online power cover problem on a line. Suppose L is a line on the plane, and S is a set of sensors on the line L, and each sensor can deploy a power and generate a covered area that can cover users. This problem is to find a minimum power assignment to cover a sequence of users on the line L arriving one by one. In this paper, we first prove that the lower bound is 2 for this problem even when \(|S|=2\) . Then, we present an online algorithm with a competitive ratio that is no more than |S| based on the greedy technique. Note that, this algorithm is the best possible online algorithm for this problem with \(|S|=2\) . Finally, we consider a special case of this problem, in which \(S=\{s_0,s_1,s_2\}\) and \(d(s_0,s_1)=d(s_1,s_2)\) , and present an online algorithm with a competitive ratio that is no more than \(\sqrt{2}+1\) .