研究了在最劣情况下，基于一个基数约束 k 最大化单调集合函数的删除问题，提出了一种新的算法 Oblivious-Greedy，并对于更广泛的非凸优化问题证明了首个常数因子逼近保证，通过提出新的度量参数，如逆曲率，证明了这些结果适用于线性区域，并通过支撑选择和方差缩小等两个实际问题的案例研究得到了验证。

Feb, 2018

本文研究了在确定性的 $ au$ 时，如何在满足固定大小约束 $k$ 的条件下最大化单调子模函数。提出了新的分区鲁棒性子模最大化算法，其构造具有指数增加大小的桶的分区，并在桶上应用标准子模优化子例程，证明了我们的算法对于更一般的 $ au = o（k）$ 具有相同的保证。在数据汇总和影响最大化方面，数值上验证了 PRo 的性能，并展示了对贪婪算法和 Orlin 等人的算法的优势。

Jun, 2017

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

Feb, 2009

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

Aug, 2018

本文考虑在噪声下最大化单调子模函数，探讨在噪声和误差存在的情况下，是否能获得算法的可证明保证，结论是对于基数约束 k>=2 的函数，有一个近似算法，其近似比例任意接近 1-1/e; 对于基数约束 k=1，有一种算法，其近似比率任意接近于 1/2。没有随机算法可以获得比 1/2+o (1) 更好的近似度；如果噪声是对抗性的，则不能获得任何非平凡的近似保证。

Jan, 2016

本文研究了在满足基数约束的条件下，最大化单调子模函数的逼近保证和适应性之间的权衡问题。我们给出了第一个使用 O（lnn /epsilon^2）轮适应性实现 1-1 /e-epsilon 逼近的算法，同时算法的函数评估次数和额外运行时间分别为 O（npoly（logn，1 /epsilon））。

Apr, 2018

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

Nov, 2023

应用阈值减小算法最大化满足 matroid 约束的 k - 次模函数，提出逼近算法来最大化满足单调和非单调 k - 次模函数，并提供了关于时间复杂度的结果，同时还介绍了针对总大小约束的快速算法。

Jul, 2023

本文讨论了带有 $d$ 背包限制的任意模子模函数最大化问题，建立了离散问题和连续松弛之间的强联系，并利用这种联系提出了近似算法和确定性技术，得到了很好的解决方案。

Jan, 2011

针对子模最大化问题，本文提出了一种动态算法，该算法对于给定序列的插入和删除操作，维护了一个在任一时间点上具有 4+ε 近似度的子系统，其参数化为 matroid 约束的秩 k，并且查找复杂度与序列长度无关；同时，我们还探讨了基于基数约束的子模最大化问题的动态算法。

Jun, 2023