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

Aug, 2018

本文提出了鲁棒次模函数最大化及其在结构组合约束下的有效算法，旨在提高对次模优化的建模范围，尤其应用于单个或多个基序，背包以及具有分散鲁棒性的标准约束条件，该算法适用于离线和在线设置，并且在线问题的双标准解决方案具有 sub-linear 的遗憾。

Oct, 2017

本文提出了单遍流式和在线算法的受约束 k - 次模最大化，其中包含基数和背包约束限制，该算法可以提供不错的近似解和高效的解决方案，并在广告分配等应用实例上得到了验证。

May, 2023

本文研究自适应子模型优化的适应性和查询复杂度，提出了适用于最大基数约束的单调子模型函数的分布式算法，并将其推广到子模型覆盖问题。

Jul, 2018

本篇论文介绍了一种新算法 FAST，旨在通过最大化满足劣模性的子模函数，使逼近比例任意接近 1-1 /e，由 O (log（n）log^2 (log k)) 次适应，总共使用 O（nloglog (k)) 次查询，在处理大数据集方面，该算法的查询复杂度和轮数都非常高效，且实验证明，FAST 比最先进的串行算法甚至是并行化的经过超级优化的状态算法都快得多。

Jul, 2019

本研究在完全动态的环境下，旨在最大化基数约束下的单调子模函数，研究结果为一个具有多项式对数的摊销更新时间和可得到 0.5-ε 近似解的随机算法，并结合经验研究证明了算法性能的优越性。

Jun, 2020

本文提出了一种适用于分布式计算的子模函数最大化方法 GreeDi，该方法可在 MapReduce 框架下实现，初步实验表明该方法可应用于大规模机器学习任务中的子模优化问题，如稀疏高斯过程推断和样例聚类等问题，且在一定的自然条件下，可以达到接近于传统集中式计算模式下的性能表现。

Nov, 2014

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

Nov, 2023

该研究主要针对单次流式处理的情况下，最大化一个非负子模集函数 f 编制一些确定性和随机算法，以实现对 p 匹配约束条件的大约 1 /p 的逼近，假设具有时间和资源约束。

Apr, 2015

本文研究基于在线变体的子模函数最大化问题，探讨了两种特殊情况并得出了竞争比的上下界。具体而言，设计了一个 $1/e$ 竞争算法和一个针对最多只包含 k 个元素的解的常数竞争比算法。

Jan, 2015