BriefGPT.xyz
May, 2023
基于拟阵的全动态次模最大化
Fully Dynamic Submodular Maximization over Matroids
HTML
PDF
Paul Dütting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Morteza Zadimoghaddam
TL;DR
研究单调子模函数下的最大值问题以及约束条件下的问题，提出了一个随机的动态算法，并给出了一个高效的数据结构来处理发生了添加和删除变化的值，该算法能够提供一个4近似解。
Abstract
Maximizing
monotone submodular functions
under a
matroid constraint
is a classic algorithmic problem with multiple applications in
data mining
→