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

Adil Erzin; Natalya Lagutkina

doi:10.1007/s11590-020-01650-8

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

Adil Erzin, Natalya Lagutkina

Department of Mechanics and Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

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 t_AP(n) is the time complexity of solving an assignment problem which is at most O(n³).

Original language	English
Number of pages	10
Journal	Optimization Letters
DOIs	https://doi.org/10.1007/s11590-020-01650-8
Publication status	Published - 10 Oct 2020

Keywords

Barrier coverage
FPTAS
Mobile sensors
COVERAGE

Access to Document

10.1007/s11590-020-01650-8

Link to publication in Scopus

Fingerprint Dive into the research topics of 'FPTAS for barrier covering problem with equal touching circles in 2D'. Together they form a unique fingerprint.

Cite this

@article{c448ec8c82734722993f1d31d767507c,

title = "FPTAS for barrier covering problem with equal touching circles in 2D",

abstract = "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).",

keywords = "Barrier coverage, FPTAS, Mobile sensors, COVERAGE",

author = "Adil Erzin and Natalya Lagutkina",

year = "2020",

month = oct,

day = "10",

doi = "10.1007/s11590-020-01650-8",

language = "English",

journal = "Optimization Letters",

issn = "1862-4472",

publisher = "Springer-Verlag GmbH and Co. KG",

}

TY - JOUR

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

AU - Erzin, Adil

AU - Lagutkina, Natalya

PY - 2020/10/10

Y1 - 2020/10/10

N2 - 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).

AB - 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).

KW - Barrier coverage

KW - FPTAS

KW - Mobile sensors

KW - COVERAGE

UR - http://www.scopus.com/inward/record.url?scp=85092364293&partnerID=8YFLogxK

U2 - 10.1007/s11590-020-01650-8

DO - 10.1007/s11590-020-01650-8

M3 - Article

AN - SCOPUS:85092364293

JO - Optimization Letters

JF - Optimization Letters

SN - 1862-4472

ER -