题目：MinSum Movement of Barrier and Target Coverage using Sink-based Mobile Sensors on the Plane

报告人：郭龙坤(福州大学)

时间：2022年7月30日(星期六)10:00

腾讯会议：568-347-555

摘要：Emerging IoT applications have brought up new coverage problems with sink-based sensors. In this paper, we first focus on the MinSum Sink-based Line Barrier Coverage (SLBC) problem of covering a line barrier with mobile sensors originated at sink stations distributed on the plane. The objective is to minimize the movement sum of the sensors for the sake of energy efficiency. When the sinks emit sensors with non-uniform radii, we prove the MinSum SLBC problem is NP-complete via reducing from the Partition problem. Then for the MinSum Sink-based on-a-Line Target Coverage (SLTC) problem of covering targets on a line, an exact algorithm is presented based on grouping the targets and transforming to the shortest path problem in the auxiliary graph induced by the vertices corresponding to the groups. Eventually for SLBC, we propose a pseudo additive fully polynomial-time approximation scheme by extending the algorithm for SLTC. At last, experiments are carried out to demonstrate the practical performance gain of the algorithms.

个人简介：郭龙坤，博士生导师，福州大学威廉体育教授。CCF理论计算机专委执行委员，数学规划学会青年理事，福建省计算机学会理事。2005与2011年分别毕业于中国科学技术大学计算机科学与技术系获工学学士与博士学位。2015年-2016年阿德莱德大学计算机学院研究工作（Research Associate）。主要研究领域包括组合优化算法设计与分析、边缘网络、分布式与云计算、大规模集成电路等。至今共发表国内外主流学术期刊与会议论文一百余篇，包括IEEE Transactions on Mobile Computing(TMC), IEEE Transactions on Computers(TC)，Algorithmica, Theoretical Computer Science, Journal of Combinatorial Optimization等国际期刊及ICDCS, ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)、International Joint Conference on Artificial Intelligence (IJCAI)等国际会议。当前主持一项国家自然科学基金面上项目与一项省部级基金；已主持完成一项国家自然科学基金青年项目与三项省部级基金（包括一项教育部博士点基金）；作为主要骨干人员加入多项国家与省部级自然科学基金。