Distance-Constrained Line Routing Problem

Adil Erzin, Roman Plotnikov

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование


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.

Язык оригиналаанглийский
Название основной публикацииOptimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers
РедакторыMilojica Jaćimović, Michael Khachay, Vlasta Malkova, Mikhail Posypkin
ИздательSpringer Gabler
Число страниц13
ISBN (печатное издание)9783030386023
СостояниеОпубликовано - 1 янв. 2020
Событие10th International Conference on Optimization and Applications, OPTIMA 2019 - Petrovac, Черногория
Продолжительность: 30 сент. 20194 окт. 2019

Серия публикаций

НазваниеCommunications in Computer and Information Science
Том1145 CCIS
ISSN (печатное издание)1865-0929
ISSN (электронное издание)1865-0937


Конференция10th International Conference on Optimization and Applications, OPTIMA 2019


Подробные сведения о темах исследования «Distance-Constrained Line Routing Problem». Вместе они формируют уникальный семантический отпечаток (fingerprint).