For constrained, not necessarily monotone submodular maximization, guiding
the measured continuous greedy algorithm with a local search algorithm
currently obtains the state-of-the-art approximation factor of 0.401
\citep{buchbinder2023constrained}. These algorithms rely upon the multilinear
extension and the Lovasz extension of a submodular set function. However, the
state-of-the-art approximation factor of combinatorial algorithms has remained
$1/e \approx 0.367$ \citep{buchbinder2014submodular}. In this work, we develop
combinatorial analogues of the guided measured continuous greedy algorithm and
obtain approximation ratio of $0.385$ in $\oh{ kn }$ queries to the submodular
set function for size constraint, and $0.305$ for a general matroid constraint.
Further, we derandomize these algorithms, maintaining the same ratio and
asymptotic time complexity. Finally, we develop a deterministic, nearly linear
time algorithm with ratio $0.377$.

本研究通过开发导向测量连续贪心算法的组合类算法，实现子模函数限制下的近似比率，同时进行去随机化处理和几乎线性时间算法的开发。

指导式组合算法用于次模最大化

Guided Combinatorial Algorithms for Submodular Maximization

A wide variety of problems in machine learning, including exemplar
clustering, document summarization, and sensor placement, can be cast as
constrained submodular maximization problems. Unfortunately, the resulting
submodular optimization problems are often too large to be solved on a single
machine. We develop a simple distributed algorithm that is embarrassingly
parallel and it achieves provable, constant factor, worst-case approximation
guarantees. In our experiments, we demonstrate its efficiency in large problems
with different kinds of constraints with objective values always close to what
is achievable in the centralized setting.

该论文提出了一个简单的分布式算法来解决在机器学习中的受限次模最大化问题，该算法可以并行运行并且提供可证明的常数近似保证，即使在单个机器上无法解决的问题也可以通过该算法高效地解决。