具近似最优适应性和查询复杂度的非单调次模最大化
本文研究了在满足基数约束的条件下,最大化单调子模函数的逼近保证和适应性之间的权衡问题。我们给出了第一个使用 O(lnn /epsilon^2)轮适应性实现 1-1 /e-epsilon 逼近的算法,同时算法的函数评估次数和额外运行时间分别为 O(npoly(logn,1 /epsilon))。
Apr, 2018
针对拥有大规模实例的问题,本文提出了第一个自适应复杂度为 O (log n),且求解非单调子模问题的背包约束问题的常数因子逼近算法,该算法提出了一个子线性适应性的组合方法,其查询值仅为 O (n)。
Feb, 2021
我们通过降低一个非单调子模函数的约束条件 k 到同样约束条件 k 下最大化一个单调子模函数,肯定回答了陈和彭提出的问题,并得到了第一个动态算法来解决非单调子模函数最大化问题。我们的算法保持了一个 (8+ε) 近似的解,并且每次更新使用预期平摊的 O (ε^-3 * k^3 * log^3 (n) * log (k)) 或者 O (ε^-1 * k^2 * log^3 (k)) 的预言查询。此外,我们展示了我们的动态算法在视频概述和基于几个真实数据集的最大割问题上的优势。
Nov, 2023
本研究提出了一种基于随机贪心算法解决非单调子模函数下的背包约束问题的方法,该算法实现了 5.83 近似和 O (nlogn) 时间复杂度;并将其转移到随机版本的问题,得到了首个非单调目标的常数近似,实验表明该方法在实际和合成数据上的性能得到了改进。
Jul, 2020
本文提出了第一个常因子近似算法来实现任何非负子模函数的最大化,同时满足多个基数约束或背包约束,特别是在 k 个划分拟阵约束下,改进了以前已知的最佳保证,获得了(1 /k+1 + 1 /k-1 + ε)的近似保证。
Feb, 2009
研究了具有健壮性约束的基数约束单调次模函数最大化问题,提出了逼近算法,并在限制相对较小的情况下,得到了相对较好的逼近结果,并应用结果解决了更普遍的独立性约束下的最大化问题。
Jul, 2015
本篇论文介绍了一种新算法 FAST,旨在通过最大化满足劣模性的子模函数,使逼近比例任意接近 1-1 /e,由 O (log(n)log^2 (log k)) 次适应,总共使用 O(nloglog (k)) 次查询,在处理大数据集方面,该算法的查询复杂度和轮数都非常高效,且实验证明,FAST 比最先进的串行算法甚至是并行化的经过超级优化的状态算法都快得多。
Jul, 2019