English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Given a line barrier and a set of mobile sensors distributed in the plane,the Minimizing Maximum Sensor Movement problem (MMSM) for\textcolor{black}{line barrier coverage} is to compute relocation positions forthe sensors in the plane such that the barrier is entirely covered by themonitoring area of the sensors while the maximum relocation movement (distance)is minimized. Its weaker version, decision MMSM is to determine whether thebarrier can be covered by the sensors within a given relocation distance bound$D\in\mathbb{Z}^{+}$.  This paper presents three approximation algorithms for decision MMSM. Thefirst is a simple greedy approach, which runs in time $O(n\log n)$ and achievesa maximum movement $D^{*}+2r_{max}$, where $n$ is the number of the sensors,$D^{*}$ is the maximum movement of an optimal solution and $r_{max}$ is themaximum radii of the sensors. The second and the third algorithms improve themaximum movement to $D^{*}+r_{max}$ , running in time $O(n^{7}L)$ and$O(R^{2}\sqrt{\frac{M}{\log R}})$ by applying linear programming (LP) roundingand maximal matching tchniques respecitvely, where $R=\sum2r_{i}$, which is$O(n)$ in practical scenarios of uniform sensing radius for all sensors, and$M\leq n\max r_{i}$. Applying the above algorithms for $O(\log(d_{max}))$ timein binary search immediately yields solutions to MMSM with the same performanceguarantee. In addition, we also give a factor-2 approximation algorithm whichcan be used to improve the performance of the first three algorithms when$r_{max}>D^{*}$. As shown in \cite{dobrev2015complexity}, the 2-D MMSM problemadmits no FPTAS as it is strongly NP-complete, so our algorithms arguablyachieve the best possible ratio.

Approximation Algorithms for Minimizing Maximum Sensor Movement for Line Barrier Coverage in the Plane