Towards Nearly-linear Time Algorithms for Submodular Maximization with a Matroid Constraint
Towards Nearly-linear Time Algorithms for Submodular Maximization with a Matroid Constraint
复制标题
DOI：
10.4230/lipics.icalp.2019.54
复制
发表时间：
2018-11
期刊：
影响因子：
--
通讯作者：
Alina Ene;Huy L. Nguyen
中科院分区：
文献类型：
--
作者：
Alina Ene;Huy L. Nguyen
我们考虑受拟阵约束的单调子模最大化的快速算法。我们假设拟阵以显式形式作为输入给出，目标是获得重要拟阵的最佳可能运行时间。我们为 \emph{一般拟阵约束} 开发了一种新算法，具有 $1 - 1/e - \epsilon$ 近似值，只要我们有一个快速数据结构，通过一系列减少权重操作来维持拟阵中的最大权重基础，即可实现快速运行时间。我们为图形拟阵和分区拟阵构建了这样的数据结构，并使用近线性数量的函数求值和算术运算，获得了这些类拟阵的 \emph{first 算法}，实现了近乎最优的 $1 - 1/e - \epsilon$ 近似。
We consider fast algorithms for monotone submodular maximization subject to a matroid constraint. We assume that the matroid is given as input in an explicit form, and the goal is to obtain the best possible running times for important matroids. We develop a new algorithm for a \emph{general matroid constraint} with a $1 - 1/e - \epsilon$ approximation that achieves a fast running time provided we have a fast data structure for maintaining a maximum weight base in the matroid through a sequence of decrease weight operations. We construct such data structures for graphic matroids and partition matroids, and we obtain the \emph{first algorithms} for these classes of matroids that achieve a nearly-optimal, $1 - 1/e - \epsilon$ approximation, using a nearly-linear number of function evaluations and arithmetic operations.