Radar placement along banks of river

Radar placement along banks of river

0.00 Avg rating0 Votes
Article ID: iaor20123058
Volume: 52
Issue: 4
Start Page Number: 729
End Page Number: 741
Publication Date: Apr 2012
Journal: Journal of Global Optimization
Authors: ,
Keywords: combinatorial optimization, programming: dynamic
Abstract:

In this paper, we consider the Radar Placement and Power Assignment problem (RPPA) along a river. In this problem, a set of crucial points in the river are required to be monitored by a set of radars which are placed along the two banks. The goal is to choose the locations for the radars and assign powers to them such that all the crucial points are monitored and the total power is minimized. If each crucial point is required to be monitored by at least k radars, the problem is a k‐Coverage RPPA problem (k‐CRPPA). Under the assumption that the river is sufficiently smooth, one may focus on the RPPA problem along a strip (RPPAS). In this paper, we present an O(n 9) dynamic programming algorithm for the RPPAS, where n is the number of crucial points to be monitored. In the special case where radars are placed only along the upper bank, we present an O(kn 5) dynamic programming algorithm for the k‐CRPPAS. For the special case that the power is linearly dependent on the radius, we present an O(n log n)‐time 2 2 equ1 ‐approximation algorithm for the RPPAS.

Reviews

Required fields are marked *. Your email address will not be published.