平面上带次模惩罚费用的最小能量部分覆盖问题

作     者：刘晓非 代涵 李思哲 李伟东 Xiaofei LIU;Han DAI;Sizhe LI;Weidong LI

作者机构：云南大学信息学院昆明650500 云南大学数学与统计学院昆明650500 华中科技大学计算机科学与技术学院武汉430074 

出 版 物：《中国科学：信息科学》 (Scientia Sinica(Informationis))

年 卷 期：2022年第52卷第6期

页      面：947-959页

核心收录：

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金(批准号:12071417)资助项目 

主　　题：能量部分覆盖问题 次模惩罚费用 原始对偶方法 半不相交 近似算法 

摘      要：给定平面上的n个用户、m个传感器和一个正整数k(≤n),任意传感器s均可以通过提供能量p(s)产生一个圆形的覆盖区域,覆盖区域的半径r(s)与p(s)满足p(s)=r(s)^(α),其中,α≥1为衰减系数.平面上带次模惩罚费用的最小能量部分覆盖问题尝试寻找传感器的一个能量供应方案,使得至少有k个用户被覆盖且总能量与未覆盖用户的惩罚费用之和达到最小,其中惩罚费用由一个次模函数确定.该问题推广了最小能量覆盖问题、最小能量部分覆盖问题和带惩罚费用的最小能量部分覆盖问题.通过深入挖掘平面上半不相交圆盘集合的几何性质,本文设计了一个基于原始对偶框架的两阶段多项式时间(5·2^(α)+1)-近似算法.当惩罚费用函数是线性函数时,此算法的近似比为5·2^(α).