Minimizing the Maximum Moving Cost of Interval Coverage.

In this paper, we consider an interval coverage problem. We are given intervals of the same length on a line and a line segment on . Each interval has a nonnegative weight. The goal is to move the intervals along such that every point of is covered by at least one interval and the maximum moving cost of all intervals is minimized, where the moving cost of each interval is its moving distance times its weight. Algorithms for the 'unweighted' version of this problem have been given before. In this paper, we present a first-known algorithm for this weighted version and our algorithm runs in time. The problem has applications in mobile sensor barrier coverage, where is the barrier and each interval is the covering interval of a mobile sensor. [ABSTRACT FROM AUTHOR]