懒惰比贪心更懒惰
本文提出了一种随机贪心算法来最大化弱次模函数在一般拟阵约束下的值,其中距离次模性的距离由参数 γ 衡量,该算法在实践中表现良好,并且是第一个能够约束弱次模函数最大化具有非平凡逼近保证的算法。
Jul, 2017
研究了 Greedy 算法在非子模不减集函数基数约束最大化中的性能,并证明了在一些重要的非子模函数如贝叶斯 A - 最优目标函数中,该算法具有很强的经验性能。我们以广义曲率 α 和子模性比率 γ 的组合为特点,证明了其理论保证,特别地,对于基数约束最大化,我们证明了 Greedy 算法具有紧密的近似保证为 1/α(1-e^(-γα))。另外,我们还限制了在几个重要的真实世界目标中子模性比率和曲率,包括贝叶斯 A - 最优目标、方形子矩阵的行列式函数和具有组合约束的某些线性规划。
Mar, 2017
通过定义锐度作为子模函数改善贪心算法性能的候选解释,本文探讨了贪心算法在最大化单调子模函数下的性能问题,显示子模函数的锐度影响贪心算法的表现,通过计算实验和理论结果,支持本文的说法。
Feb, 2020
本研究以连续贪心算法为基础,研究了具有一般性骨架约束的随机子模最大化问题,主要应用于在线学习,团队形成,设施位置,影响最大化,主动学习和感知目标函数。实验表明,使用多项式梯度估计代替样本估计,可有效减少随机性并缩短执行时间。
Mar, 2023
本文介绍了针对具有限制条件的子模函数进行最大化的两种算法 ——Repeated Greedy 和 Sample Greedy,并比较了这两种算法在电影推荐方面的表现。结果表明,Sample Greedy 在保证效用相同的情况下,性能至少比最佳基线提高了两个数量级。
Apr, 2017
本研究提出了一种基于随机贪心算法解决非单调子模函数下的背包约束问题的方法,该算法实现了 5.83 近似和 O (nlogn) 时间复杂度;并将其转移到随机版本的问题,得到了首个非单调目标的常数近似,实验表明该方法在实际和合成数据上的性能得到了改进。
Jul, 2020
研究了具有健壮性约束的基数约束单调次模函数最大化问题,提出了逼近算法,并在限制相对较小的情况下,得到了相对较好的逼近结果,并应用结果解决了更普遍的独立性约束下的最大化问题。
Jul, 2015
本文研究在流式场景下,求解具有基数限制 k 的单调子模函数最大化问题,提出了一种基于 STAR-T 算法的新型分区结构和指数递减阈值规则,这种算法只需要一次遍历数据,即可保留简短而健壮的总结性概括,还证明了在删除汇总得到的任何 m 个元素后,基于剩余的元素运行的一种简单贪心算法 STAR-T-GREEDY 可获得近似,最后通过两项不同的数据汇总任务证明了 STAR-T 的性能媲美先前的贪心和流式方法。
Nov, 2017
我们通过降低一个非单调子模函数的约束条件 k 到同样约束条件 k 下最大化一个单调子模函数,肯定回答了陈和彭提出的问题,并得到了第一个动态算法来解决非单调子模函数最大化问题。我们的算法保持了一个 (8+ε) 近似的解,并且每次更新使用预期平摊的 O (ε^-3 * k^3 * log^3 (n) * log (k)) 或者 O (ε^-1 * k^2 * log^3 (k)) 的预言查询。此外,我们展示了我们的动态算法在视频概述和基于几个真实数据集的最大割问题上的优势。
Nov, 2023
研究了在最劣情况下,基于一个基数约束 k 最大化单调集合函数的删除问题,提出了一种新的算法 Oblivious-Greedy,并对于更广泛的非凸优化问题证明了首个常数因子逼近保证,通过提出新的度量参数,如逆曲率,证明了这些结果适用于线性区域,并通过支撑选择和方差缩小等两个实际问题的案例研究得到了验证。
Feb, 2018