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
Страницы43-55
Число страниц13
ISBN (печатное издание)9783030386023
DOI
СостояниеОпубликовано - 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
СтранаЧерногория
ГородPetrovac
Период30.09.201904.10.2019

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

  • Цитировать

    Erzin, A., & Plotnikov, R. (2020). Distance-Constrained Line Routing Problem. В M. Jaćimović, M. Khachay, V. Malkova, & M. Posypkin (Ред.), Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers (стр. 43-55). (Communications in Computer and Information Science; Том 1145 CCIS). Springer Gabler. https://doi.org/10.1007/978-3-030-38603-0_4