论文标题
完全动态算法，用于受约束的下二次优化
Fully Dynamic Algorithm for Constrained Submodular Optimization
论文作者
论文摘要
在基数限制下最大化单调下调功能的任务是许多机器学习和数据挖掘应用程序的核心，包括数据摘要，稀疏回归和覆盖范围问题。我们在完全动态的环境中研究了这个经典问题，可以在其中插入和去除元素。我们的主要结果是一种随机算法，该算法以多层摊销更新时间维护有效的数据结构，并产生$（1/2-ε）$ - 近似解决方案。我们通过对算法的性能进行实证研究来补充理论分析。
The task of maximizing a monotone submodular function under a cardinality constraint is at the core of many machine learning and data mining applications, including data summarization, sparse regression and coverage problems. We study this classic problem in the fully dynamic setting, where elements can be both inserted and removed. Our main result is a randomized algorithm that maintains an efficient data structure with a poly-logarithmic amortized update time and yields a $(1/2-ε)$-approximate solution. We complement our theoretical analysis with an empirical study of the performance of our algorithm.
