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

Jun, 2017

本文主要研究如何在保护用户隐私和确保公平性的同时，高效地从大型用户生成的数据集中提取有用信息。该问题被描述成删除鲁棒子模型最大化的一个实例，我们提出了第一种内存高效的集中式、流式和分布式方法，对任意数量的敌对删除具有常数逼近保证。我们对我们的算法在真实世界的应用进行了广泛评估，包括：（i）具有位置隐私限制的Uber接送点；（ii）收入预测和犯罪率预测的公平性限制的特征选择；以及(iii)由2,458,285个特征向量组成的人口普查数据的删除汇总结果的健壮性。

Nov, 2017

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

Feb, 2018

该研究提出了针对单个和多个背包约束下的单调次模最大化的首个对抗鲁棒算法，具有可扩展的分布式和流式实现。性能评估结果表明，与现有非鲁棒算法的自然鲁棒化相比，该算法对于大型社交网络图等输入具有最佳的目标结果，并表现出极强的性能，即使与提前给出拆除集合的线下算法相比也是如此。

May, 2019

针对拥有大规模实例的问题，本文提出了第一个自适应复杂度为 O(log n)，且求解非单调子模问题的背包约束问题的常数因子逼近算法，该算法提出了一个子线性适应性的组合方法，其查询值仅为O(n)。

Feb, 2021

该研究探讨基于经典拟阵约束下的删除鲁棒版本的子模函数最大化问题，在此问题中，目标是提取一个小型数据集的摘要，即使在对手删除一些元素后也包含高价值独立集，该研究提供了具有常数因子逼近比的近似算法，其中空间复杂度取决于拟阵的秩k和已删除元素的数量d。

Aug, 2022

研究单调子模函数下的最大值问题以及约束条件下的问题，提出了一个随机的动态算法，并给出了一个高效的数据结构来处理发生了添加和删除变化的值，该算法能够提供一个4近似解。

May, 2023

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

Jun, 2023

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

Jul, 2023

在机器学习中，基于 matroid 约束的子模最大化是一个具有各种应用的基本问题。最近，已经在有限制条件下的流式和离线设置下考虑了基于基数约束的子模最大化中的公平性，但对于更一般的 matroid 约束问题，只有在流式设置下且只考虑单调目标。本文通过提出各种算法和不可能性结果，在质量、公平性和广泛性之间提供了不同的权衡。

Dec, 2023