BriefGPT.xyz
Jan, 2022
基于拟阵的删除鲁棒子模型最大化
Deletion Robust Submodular Maximization over Matroids
HTML
PDF
Paul Dütting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Morteza Zadimoghaddam
TL;DR
本文研究在传统的拟阵约束下，单调子模函数的删除鲁棒版本的最大化问题，提出了空间复杂度依赖于拟阵的秩和删除元素数量的常数因子逼近算法，在中心化、流式环境下均获得了好的结果。
Abstract
Maximizing a monotone
submodular function
is a fundamental task in machine learning. In this paper, we study the
deletion robust
version of the problem under the classic matroids constraint. Here the goal is to e
→