This paper considers a movement minimization problem for mobile sensors. Given a set of n point targets, the k-Sink Minimum Movement Target Coverage Problem is to schedule mobile sensors, initially located at k base stations, to cover all targets minimizing the total moving distance of the sensors. We present a polynomial-time approximation scheme for finding a <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2024_1253_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="49" /> </InlineMediaObject> <EquationSource Format="TEX">$(1+\epsilon )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <mi>ϵ</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> approximate solution running in time <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2024_1253_Article_IEq2.gif" Format="GIF" Height="18" Rendition="HTML" Resolution="72" Type="Linedraw" Width="47" /> </InlineMediaObject> <EquationSource Format="TEX">$n^{O(1/\epsilon )}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>n</mi> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">/</mo> <mi>ϵ</mi> <mo stretchy="false">)</mo> </mrow> </msup> </math></EquationSource> </InlineEquation> for this problem when k, the number of base stations, is constant. Our algorithm improves the running time exponentially from the previous work that runs in time <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2024_1253_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="52" /> </InlineMediaObject> <EquationSource Format="TEX">$n^{O(1/\epsilon ^2)}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>n</mi> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">/</mo> <msup> <mi>ϵ</mi> <mn>2</mn> </msup> <mo stretchy="false">)</mo> </mrow> </msup> </math></EquationSource> </InlineEquation>, without any target distribution assumption. To devise a faster algorithm, we prove a stronger bound on the number of sensors in any unit area in the optimal solution and employ a more refined dynamic programming algorithm whose complexity depends only on the width of the problem.

An improved PTAS for covering targets with mobile sensors

期刊论文
发表日期：

2025年1月20日

查看全文

Nonthaphat Wongwattanakij,
Nattawut Phetmak,
Chaiporn Jaikaeo,
Jittat Fakcharoenphol

摘要

This paper considers a movement minimization problem for mobile sensors. Given a set of n point targets, the k-Sink Minimum Movement Target Coverage Problem is to schedule mobile sensors, initially located at k base stations, to cover all targets minimizing the total moving distance of the sensors. We present a polynomial-time approximation scheme for finding a $(1+\epsilon )$ $(1 + ϵ)$ approximate solution running in time $n^{O(1/\epsilon )}$ $n^{O (1 / ϵ)}$ for this problem when k, the number of base stations, is constant. Our algorithm improves the running time exponentially from the previous work that runs in time $n^{O(1/\epsilon ^2)}$ $n^{O (1 / ϵ^{2})}$ , without any target distribution assumption. To devise a faster algorithm, we prove a stronger bound on the number of sensors in any unit area in the optimal solution and employ a more refined dynamic programming algorithm whose complexity depends only on the width of the problem.