论文标题
最低稳健的多型盖盖
Minimum Robust Multi-Submodular Cover for Fairness
论文作者
论文摘要
在本文中，我们研究了一个新的问题，最小稳健的多种模型覆盖公平性（MINRF），如下所示：给定地面套装$ v $； $ m $单调supdoular函数$ f_1，...，f_m $; $ m $ thresholds $ t_1，...，t_m $和非负整数$ r $，minrf要求最小的集合$ s $，以便所有$ i \ in [m] $，$ \ min_ {| x | x | \ leq r} f_i（s \ setminus x）\ geq t_i $。我们证明，MinRF在$（1-ε）\ ln m $之内不适合;而且，没有算法，少于$ r $的查询数量少，它能够以很高的确定性输出可行的设置。提出了三种具有性能保证的双晶型近似算法：一个用于$ r = 0 $，$ r = 1 $，一种用于一般$ r $。我们进一步研究了算法在MINRF的两个应用程序中的性能，多个组的信息传播以及对多个用户的电影推荐。在大多数情况下，我们的算法已显示出在解决方案质量和查询数量方面的表现均优于基线启发式方法。
In this paper, we study a novel problem, Minimum Robust Multi-Submodular Cover for Fairness (MinRF), as follows: given a ground set $V$; $m$ monotone submodular functions $f_1,...,f_m$; $m$ thresholds $T_1,...,T_m$ and a non-negative integer $r$, MinRF asks for the smallest set $S$ such that for all $i \in [m]$, $\min_{|X| \leq r} f_i(S \setminus X) \geq T_i$. We prove that MinRF is inapproximable within $(1-ε)\ln m$; and no algorithm, taking fewer than exponential number of queries in term of $r$, is able to output a feasible set to MinRF with high certainty. Three bicriteria approximation algorithms with performance guarantees are proposed: one for $r=0$, one for $r=1$, and one for general $r$. We further investigate our algorithms' performance in two applications of MinRF, Information Propagation for Multiple Groups and Movie Recommendation for Multiple Users. Our algorithms have shown to outperform baseline heuristics in both solution quality and the number of queries in most cases.
