论文标题
通过贪婪和进化帕累托优化的强大子集选择
Robust Subset Selection by Greedy and Evolutionary Pareto Optimization
论文作者
论文摘要
旨在从地面集中选择子集以最大化某些目标函数的子集选择是在各种应用中出现的，例如影响最大化和传感器放置。但是，在实际情况下，人们通常需要找到一个因不确定性而导致的许多可能的目标函数（即良好的）子集，从而导致了可靠的子集选择问题。本文认为具有单调目标函数的强大子集选择，从而放宽了先前研究所需的子模型。我们首先表明，贪婪算法可以获得$ 1-E^{ - βγ} $的近似值，其中$β$和$β$和$γ$分别是目标函数的相关性和次数比率；然后提出Eporss，这是一种进化的帕累托优化算法，可以利用更多的时间找到更好的子集。我们证明，在理论上也可以基于基础，从而获得与贪婪算法相似的近似保证。此外，我们得出了$β$的下限，以实现鲁棒的影响最大化，并进一步进行实验以验证贪婪算法和Eporss的性能。
Subset selection, which aims to select a subset from a ground set to maximize some objective function, arises in various applications such as influence maximization and sensor placement. In real-world scenarios, however, one often needs to find a subset which is robust against (i.e., is good over) a number of possible objective functions due to uncertainty, resulting in the problem of robust subset selection. This paper considers robust subset selection with monotone objective functions, relaxing the submodular property required by previous studies. We first show that the greedy algorithm can obtain an approximation ratio of $1-e^{-βγ}$, where $β$ and $γ$ are the correlation and submodularity ratios of the objective functions, respectively; and then propose EPORSS, an evolutionary Pareto optimization algorithm that can utilize more time to find better subsets. We prove that EPORSS can also be theoretically grounded, achieving a similar approximation guarantee to the greedy algorithm. In addition, we derive the lower bound of $β$ for the application of robust influence maximization, and further conduct experiments to validate the performance of the greedy algorithm and EPORSS.
