FPTAS for barrier covering problem with equal touching circles in 2D

Adil Erzin, Natalya Lagutkina

Результат исследования: Научные публикации в периодических изданияхстатьярецензирование

Аннотация

In this paper, we consider a problem of optimal covering a barrier in the form of a line segment with equal circles distributed in a plane by moving their centers onto the segment or the line containing a segment. We require the neighboring circles in the cover to touch each other. The objective is to minimize the total traveled by circles Euclidian distance. The complexity status of the problem is not known. We propose an O(tAP(n)ε2)–time FPTAS for the problem, where n is the number of circles and tAP(n) is the time complexity of solving an assignment problem which is at most O(n3).

Язык оригиналаанглийский
Страницы (с-по)1397-1406
Число страниц10
ЖурналOptimization Letters
Том15
Номер выпуска4
DOI
СостояниеОпубликовано - июн 2021

Предметные области OECD FOS+WOS

  • 5.02.PE ИССЛЕДОВАНИЕ ОПЕРАЦИЙ И НАУКА УПРАВЛЕНИЯ
  • 1.01.PQ МАТЕМАТИКА

Fingerprint

Подробные сведения о темах исследования «FPTAS for barrier covering problem with equal touching circles in 2D». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать