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

Standard

FPTAS for barrier covering problem with equal touching circles in 2D. / Erzin, Adil; Lagutkina, Natalya.

In: Optimization Letters, Vol. 15, No. 4, 06.2021, p. 1397-1406.

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

Harvard

Erzin, A & Lagutkina, N 2021, 'FPTAS for barrier covering problem with equal touching circles in 2D', Optimization Letters, vol. 15, no. 4, pp. 1397-1406. https://doi.org/10.1007/s11590-020-01650-8

APA

Erzin, A., & Lagutkina, N. (2021). FPTAS for barrier covering problem with equal touching circles in 2D. Optimization Letters, 15(4), 1397-1406. https://doi.org/10.1007/s11590-020-01650-8

Vancouver

Erzin A, Lagutkina N. FPTAS for barrier covering problem with equal touching circles in 2D. Optimization Letters. 2021 Jun;15(4):1397-1406. doi: 10.1007/s11590-020-01650-8

Author

Erzin, Adil ; Lagutkina, Natalya. / FPTAS for barrier covering problem with equal touching circles in 2D. In: Optimization Letters. 2021 ; Vol. 15, No. 4. pp. 1397-1406.

BibTeX

@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",

}

RIS

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 -

ID: 25686380