A distributed algorithm for partitioned robust submodular maximization
A distributed algorithm for partitioned robust submodular maximization
复制标题
一种用于分区鲁棒子模最大化的分布式算法
DOI：
10.1109/camsap.2017.8313155
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
V. Cevher
中科院分区：
文献类型：
--
作者：
Ilija Bogunovic;Slobodan Mitrovic;J. Scarlett;V. Cevher
在本文中，我们考虑了在基数约束下最大化单调子模函数的问题，并增加了两个变化：计算分布在许多机器上，并且我们要求解决方案对于对抗性删除具有鲁棒性。我们针对这个问题提供了两个版本的分区鲁棒算法，其区别在于是否通知集中式机器（仅在算法的最后阶段）哪些元素将被删除。在这两种情况下，我们都针对最优算法提供了一种新颖的常数因子近似保证。最后，我们通过影响最大化和数据汇总方面的真实数据集的数值实验来验证我们的算法。
In this paper, we consider the problem of maximizing a monotone submodular function subject to a cardinality constraint, with two added twists: The computation is distributed across a number of machines, and we require the solution to be robust against adversarial removals. We provide two versions of a partitioned robust algorithm for this problem, with the difference amounting to whether or not the centralized machine is informed (only in the final stage of the algorithm) which elements will be removed. In both of these cases, we provide a novel constant-factor approximation guarantee with respect to the optimal algorithm. Finally, we validate our algorithms via numerical experiments on real-world data sets in influence maximization and data summarization.
DOI：
--
发表时间：
2015-02
期刊：
ArXiv
影响因子：
--
作者：
R. Barbosa;Alina Ene;Huy L. Nguyen;Justin Ward
通讯作者：
R. Barbosa;Alina Ene;Huy L. Nguyen;Justin Ward