Page 494 - 《软件学报》2025年第7期

张朋飞 等: 基于自适应剪枝的满足本地差分隐私的真值发现算法 3415

由于 WSCP 是 NP-hard 的, 便可以证明公式 (22) 所示的剪枝问题也是 NP-hard 的.
首先给出 WSCP 的判定问题. 假定希望下载到 k 个需要的科研软件, 这些软件的集合为 U. S 为科研软件的下
载镜像, 包含第 i 个软件的下载站为 S i , 该站点的下载速度为 , 且 S i 中能下载的软件集合包含在 U 中. 如何确定
v i
下载软件的站点集合才能覆盖到 U 中所有软件并使总的下载速度最大.
其次将公式 (22) 所示剪枝问题规约为 WSCP. 具体地讲, 待覆盖的 N 个任务可以看作是软件集合 U, 每个工

人做的任务集合可以看做 S i , 每个任务的重要性 y n 可以看作是站点的下载速度 . 由于, 公式 (22) 还需要考虑工
v i
人的质量, 因此, 上述剪枝问题可以看作是更复杂的 WSCP 问题. 公式 (22) 所述的剪枝问题也是 NP-hard 的.
(2) 多项式时间复杂度的算法设计
由于剪枝问题的 NP-hard 特性, 本文需要设计出具有多项式时间复杂度的算法. 根据文献 [26], 所有任务隐私
保护前后的平均绝对误差如公式 (23):

 √ 
1 N ∑  d 2 −d 1 2  

MAE ≈    + σ avg   (23)
N  ε π 
n=1
其中, N 表示该任务的数量, σ avg 表示某个任务的平均误差, d 1 和 d 2 表示某个任务域值的最小值和最大值.
1
再者, 根据文献 [6], σ avg ∝ , 那么对于工人, 本文有:
w 2
avg
 ∑ M 1 
 
 √ 
 
1 N ∑  d 2 −d 1 2 s=1 w 
2 

MAE u ≈    + s     (24)
N    ε π M   
n=1    
由于 d 1 和 d 2 等都为常量, 那么:

1
M ∑
w 2
s=1 s
MAE u ∝ (25)
M
那么, 为了对工人数据进行剪枝, 我们有如下定理 5.
定理 5. 给定质量从大到小排序好的工人集合, 从最小质量的工人开始剪枝. 假如 K 为剩余的工人数量, 如果
满足公式 (26), 则停止剪枝.

1 1
K ∑
⩾ K (26)
w 2 w 2
s=1 s K+1
1
,
证明: 已知 1 ⩽ K ⩽ M −1 w 1 ⩾ w K ⩾ w M , 设辅助变量 z s = . 根据公式 (24), 前 K 个工人被保留时候的总体误
w 2 s
差如公式 (27) 所示:

K ∑
z s
s=1
MAE K ∝ (27)
K
如果第 K+1 个工人也被保留, 那么总体误差为:

K ∑
z s +z K+1
s=1
MAE K+1 ∝ (28)
K +1
如果第 K+1 MAE K ⩾ MAE K+1 , 得到:
个工人不被剪枝, 也就是说加上该工人后误差变小, 那么令
K ∑
z s −z K+1 K
s=1
MAE K − MAE K+1 = (29)
K (K +1)
K ∑
由于 K (K +1) > 0, 因此, 如果 z s ⩾ z K+1 K, 那么 MAE K ⩾ MAE K+1 .
s=1