FPTAS for barrier covering problem with equal circles in 2D

November 26, 2018 Β· Declared Dead Β· πŸ› arXiv.org

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Adil Erzin, Natalya Lagutkina arXiv ID 1811.10161 Category cs.DS: Data Structures & Algorithms Citations 2 Venue arXiv.org Last Checked 4 months ago
Abstract
In this paper, we consider a problem of covering a straight line segment by equal circles that are initially arbitrarily placed on a plane by moving their centers on a segment or on a straight line containing a segment so that the segment is completely covered, the neighboring circles in the cover are touching each other and the total length of the paths traveled by circles is minimal. The complexity status of the problem is not known. We propose a $O(n^{2+c}/\varepsilon^2)$--time FPTAS for this problem, where $n$ is the number of circles and $c>0$ is arbitrarily small real.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Data Structures & Algorithms

Died the same way β€” πŸ‘» Ghosted