Order Preserving Barrier Coverage with Weighted Sensors on a Line
| Autor: | Robert Benkoczi, Xiao Zhang, Daya Ram Gaur |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Polynomial
Computer science Generalization Order (ring theory) 0102 computer and information sciences 02 engineering and technology Computational geometry Binary logarithm Topology 01 natural sciences Line segment 010201 computation theory & mathematics Line (geometry) 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Focus (optics) |
| Zdroj: | Algorithmic Aspects in Information and Management ISBN: 9783030046170 AAIM |
| DOI: | 10.1007/978-3-030-04618-7_20 |
| Popis: | We consider a barrier coverage problem with heterogeneous mobile sensors where the sensors are located on a line and the goal is to move the sensors so that a given line segment, called the barrier, is covered by the sensors. We focus on an important generalization of the classical model where the cost of moving a sensor equals the weighted travel distance and the sensor weights are arbitrary. For the objective of minimizing the maximum cost of moving a sensor, it was recently shown that the problem is NP-hard when the sensing ranges are arbitrary. In contrast, Chen et al. give an \(O(n^2 \log n)\) algorithm for the problem with uniform weights and arbitrary sensing ranges. Xiao shows that restricting the problem to uniform sensing ranges but allowing arbitrary sensor weights can also be solved exactly in time \(O(n^2 \log n \log \log n)\), raising the question whether other restrictions can be solved in time polynomial in the size of the instance. In this paper, we show that a natural restriction in which sensors must preserve their relative ordering (the sensors move on rails, for example) but the sensors have arbitrary sensing ranges and weights can be solved in time \((n^2 \log ^3 n)\). Due to the combinatorially rich set of configurations of the optimal solution for our problem, our algorithm uses the general parametric search method of Megiddo which parameterizes a feasibility test algorithm. Interestingly, it is not easy to design an efficient feasibility test algorithm for the order preserving problem. We overcome the difficulties using the concept of critical budget values and employing standard computational geometry techniques. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|