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

作者：刘晓非; 代涵; 李思哲; 李伟东^*

来源：中国科学:信息科学 , 2022, 52(06): 947-959.

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

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

• 单位
  华中科技大学; 云南大学