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
Pages (from-to)	1397-1406
Number of pages	10
Journal	Optimization Letters
Volume	15
Issue number	4
DOIs	https://doi.org/10.1007/s11590-020-01650-8
Publication status	Published - Jun 2021

Keywords

Barrier coverage
FPTAS
Mobile sensors
COVERAGE

OECD FOS+WOS

5.02.PE OPERATIONS RESEARCH & MANAGEMENT SCIENCE
1.01.PQ MATHEMATICS

Access to Document

10.1007/s11590-020-01650-8

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 = "2021",

month = jun,

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

language = "English",

volume = "15",

pages = "1397--1406",

journal = "Optimization Letters",

issn = "1862-4472",

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

number = "4",

}

TY - JOUR

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

AU - Erzin, Adil

AU - Lagutkina, Natalya

PY - 2021/6

Y1 - 2021/6

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

VL - 15

SP - 1397

EP - 1406

JO - Optimization Letters

JF - Optimization Letters

SN - 1862-4472

IS - 4

ER -

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

Abstract

Keywords

OECD FOS+WOS

Access to Document

Other files and links

Fingerprint

Cite this