本文提出了第一个常因子近似算法来实现任何非负子模函数的最大化，同时满足多个基数约束或背包约束，特别是在 k 个划分拟阵约束下，改进了以前已知的最佳保证，获得了（1 /k+1 + 1 /k-1 + ε）的近似保证。

Feb, 2009

本研究提出了一种基于随机贪心算法解决非单调子模函数下的背包约束问题的方法，该算法实现了 5.83 近似和 O (nlogn) 时间复杂度；并将其转移到随机版本的问题，得到了首个非单调目标的常数近似，实验表明该方法在实际和合成数据上的性能得到了改进。

Jul, 2020

非单调子模最大化问题和打包约束下的子模并行算法设计优化和逼近

Aug, 2023

提出了两个确定性近似算法来解决非单调 k - 次模极大化问题，其在查询复杂度仅为 O (nk) 的情况下提供了常数近似比率，比现有算法少使用了 Omega (log n) 数量的查询。

Sep, 2023

提出一种用于最大化满足背包限制下单调子模函数的算法，并且该算法的多项式时间复杂度为一个取决于输入函数曲率 c 的比率，该算法的近似度为 1-c/e-ε，这一近似度对于任何处于区间 [0,1] 中的 c 值均是紧确的。此外，该研究提供了用于预算分配问题的多项式时间算法，并且有一种更好的近似度。

Jul, 2016

在本研究中，我们考虑了基于背包约束的子模型最大化问题，该问题涉及大小为 n 的总体。我们将最快确定性算法的近似因子从 6+ε 改进为 5+ε，同时保持了 O (n) 的最佳查询复杂度。我们的技术是基于两个组件的性能优化：阈值贪婪子程序和建立两个不相交集合作为候选解。此外，通过仔细分析候选解的成本，我们获得了更紧的近似因子。

May, 2024

本文提出了一种在单个 matroid 约束或多个 packing 约束下，通过小量自适应查询轮次来最大化 submodular 函数的多线性扩展的算法，该算法在 submodular maximization with a matroid constraint 和 non-monotone submodular maximization subject to packing constraints 两个问题上均获得了近乎最佳的拟合比例，并且在自适应轮次和并行运行时间上提出了指数级别的加速。

Aug, 2018

我们通过降低一个非单调子模函数的约束条件 k 到同样约束条件 k 下最大化一个单调子模函数，肯定回答了陈和彭提出的问题，并得到了第一个动态算法来解决非单调子模函数最大化问题。我们的算法保持了一个 (8+ε) 近似的解，并且每次更新使用预期平摊的 O (ε^-3 * k^3 * log^3 (n) * log (k)) 或者 O (ε^-1 * k^2 * log^3 (k)) 的预言查询。此外，我们展示了我们的动态算法在视频概述和基于几个真实数据集的最大割问题上的优势。

Nov, 2023

研究分布式情况下近似最大化非单调子模函数时算法适应性和查询复杂度的方法及其应用

Aug, 2018

研究了具有健壮性约束的基数约束单调次模函数最大化问题，提出了逼近算法，并在限制相对较小的情况下，得到了相对较好的逼近结果，并应用结果解决了更普遍的独立性约束下的最大化问题。

Jul, 2015