Online Range Assignment Problems
摘要
We study two online range assignment problems. In the first problem, introduced by de Berg et al. [4], P is a growing set of transceivers, initially consisting of a single transceiver \(p_1\) . Upon the arrival of a new transceiver \(p_i\) , one needs to (re)assign a range to at most one of the ‘previous’ transceivers, so that \(p_i\) is covered by at least one of them. We adopt the common rule that a transceiver’s range (which is initially 0) can never decrease over time. The cost of such an online range assignment is \(\sum _{i = 1}^n \rho (p_i)\) , where \(\rho (p_i)\) is the final range assigned to \(p_i\) , and we wish to compare it with the cost of an optimal offline assignment which satisfies the intermediate coverage requirements. We present several results for this problem, which improve some of the previous results of de Berg et al. [4]. We also introduce a new problem, in which we have a set T of stationary transmitters and an initially-empty set S of mobile receivers. Upon the arrival of a new receiver s, it must first specify its intended route, after which one needs to (re)assign a range to at most one of the transmitters in T, so that s’s route is fully covered by at least one of them. We consider the case where the routes of the receivers are unit line segments and prove a constant factor upper bound on the competitive ratio of our range assignment algorithm.