Adversarially Robust Submodular Maximization under Knapsack Constraints
Adversarially Robust Submodular Maximization under Knapsack Constraints
复制标题
DOI：
10.1145/3292500.3330911
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Dmitrii Avdiukhin;Slobodan Mitrovic;G. Yaroslavtsev;Samson Zhou
中科院分区：
文献类型：
--
作者：
Dmitrii Avdiukhin;Slobodan Mitrovic;G. Yaroslavtsev;Samson Zhou
我们提出了第一个adversarially强大的算法，单调子模块最大化下的单个和多个背包的约束，可扩展的实现在分布式和流媒体设置。对于一个单一的背包约束，我们的算法输出一个强大的总结几乎最佳（多对数因子）的大小，从中可以构建一个常数因子近似的最优解。对于多个背包约束，我们的近似值在最佳已知非鲁棒解的常数因子范围内。我们评估我们的算法的性能比较现有的非鲁棒算法的自然鲁棒性下两个目标：1）支配集的大型社交网络图从Facebook和Twitter收集的斯坦福大学网络分析项目（SNAP），2）电影推荐的数据集MovieLens。实验结果表明，我们的算法给出了最好的目标，为大多数的输入，并显示出强大的性能，即使离线算法，预先给定的一组删除。
We propose the first adversarially robust algorithm for monotone submodular maximization under single and multiple knapsack constraints with scalable implementations in distributed and streaming settings. For a single knapsack constraint, our algorithm outputs a robust summary of almost optimal (up to polylogarithmic factors) size, from which a constant-factor approximation to the optimal solution can be constructed. For multiple knapsack constraints, our approximation is within a constant-factor of the best known non-robust solution. We evaluate the performance of our algorithms by comparison to natural robustifications of existing non-robust algorithms under two objectives: 1) dominating set for large social network graphs from Facebook and Twitter collected by the Stanford Network Analysis Project (SNAP), 2) movie recommendations on a dataset from MovieLens. Experimental results show that our algorithms give the best objective for a majority of the inputs and show strong performance even compared to offline algorithms that are given the set of removals in advance.