TY - GEN
T1 - Distance-Constrained Line Routing Problem
AU - Erzin, Adil
AU - Plotnikov, Roman
N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2020.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2020/1/1
Y1 - 2020/1/1
N2 - On the plane, the barrier is a line segment, and the mobile sensors are initially located at some points (depots). Each sensor can travel a limited-length path, starting and ending at its depot. That part of the barrier, along which sensor moved, is covered by this sensor. It is required to find a min-power subset of sensors covering the entire barrier. The complexity of this problem is not known. In this paper, we have found the special cases of polynomial solvability and state some necessary and sufficient conditions for the existence of the solution. An efficient (polynomial) algorithm for checking the existence of the solution is proposed. Moreover, we have developed some approximation algorithms. In particular, an efficient implementation of the dynamic programming algorithm, which in some special cases yields an optimal solution, is proposed.
AB - On the plane, the barrier is a line segment, and the mobile sensors are initially located at some points (depots). Each sensor can travel a limited-length path, starting and ending at its depot. That part of the barrier, along which sensor moved, is covered by this sensor. It is required to find a min-power subset of sensors covering the entire barrier. The complexity of this problem is not known. In this paper, we have found the special cases of polynomial solvability and state some necessary and sufficient conditions for the existence of the solution. An efficient (polynomial) algorithm for checking the existence of the solution is proposed. Moreover, we have developed some approximation algorithms. In particular, an efficient implementation of the dynamic programming algorithm, which in some special cases yields an optimal solution, is proposed.
KW - Barrier covering
KW - Distance-constrained line routing
KW - Mobile sensors
UR - http://www.scopus.com/inward/record.url?scp=85078398234&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-38603-0_4
DO - 10.1007/978-3-030-38603-0_4
M3 - Conference contribution
AN - SCOPUS:85078398234
SN - 9783030386023
T3 - Communications in Computer and Information Science
SP - 43
EP - 55
BT - Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers
A2 - Jaćimović, Milojica
A2 - Khachay, Michael
A2 - Malkova, Vlasta
A2 - Posypkin, Mikhail
PB - Springer Gabler
T2 - 10th International Conference on Optimization and Applications, OPTIMA 2019
Y2 - 30 September 2019 through 4 October 2019
ER -