Apr, 2017

贪心是美德：通过贪心优化实现近似最优子模函数最大化

PDF
TL;DR本文介绍了针对具有限制条件的子模函数进行最大化的两种算法 ——Repeated Greedy 和 Sample Greedy，并比较了这两种算法在电影推荐方面的表现。结果表明，Sample Greedy 在保证效用相同的情况下，性能至少比最佳基线提高了两个数量级。
greedy algorithmsubmodular functionsystem constraintsapproximationmovie recommendation
发现论文，激发创造
  • 懒惰比贪心更懒惰

    本文提出了一种线性时间算法 STOCHASTIC-GREEDY 用于求解一般性单调子模函数最大化问题，旨在实现对数据的概括，比传统算法 lazy greedy 更快且表现基本一致。

    Sep, 2014

  • 非子模函数的贪心最大化保证及应用

    研究了 Greedy 算法在非子模不减集函数基数约束最大化中的性能，并证明了在一些重要的非子模函数如贝叶斯 A - 最优目标函数中，该算法具有很强的经验性能。我们以广义曲率 α 和子模性比率 γ 的组合为特点，证明了其理论保证，特别地，对于基数约束最大化，我们证明了 Greedy 算法具有紧密的近似保证为 1/α(1-e^(-γα))。另外，我们还限制了在几个重要的真实世界目标中子模性比率和曲率，包括贝叶斯 A - 最优目标、方形子矩阵的行列式函数和具有组合约束的某些线性规划。

    Mar, 2017

  • 非子模目标强鲁棒性最大化

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

    Feb, 2018

  • 针对背包约束的快速自适应非单调子模型最大化

    本研究提出了一种基于随机贪心算法解决非单调子模函数下的背包约束问题的方法，该算法实现了 5.83 近似和 O (nlogn) 时间复杂度；并将其转移到随机版本的问题，得到了首个非单调目标的常数近似，实验表明该方法在实际和合成数据上的性能得到了改进。

    Jul, 2020

  • 贪心算法的不合理有效性：贪心算法适应尖锐度

    通过定义锐度作为子模函数改善贪心算法性能的候选解释，本文探讨了贪心算法在最大化单调子模函数下的性能问题，显示子模函数的锐度影响贪心算法的表现，通过计算实验和理论结果，支持本文的说法。

    Feb, 2020

  • 超越基数约束的弱次模最大化：贪心法是否受益于随机化？

    本文提出了一种随机贪心算法来最大化弱次模函数在一般拟阵约束下的值，其中距离次模性的距离由参数 γ 衡量，该算法在实践中表现良好，并且是第一个能够约束弱次模函数最大化具有非平凡逼近保证的算法。

    Jul, 2017

  • 超模极大化 —— 非非负性保证、快速算法和应用

    本文研究次模函数的优化和算法问题，提出了一种在 $k$-cardinality 约束下最大化 $g-c$ 的算法，并通过实验设计对其进行了验证。

    Apr, 2019

  • 鲁棒子模最大化：一种非均匀划分方法

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

    Jun, 2017

  • 带有分割骨架约束的曲率有界函数贪心最大化

    本研究探讨了确定性 GREEDY 算法在分区拟阵约束下的函数最大化问题中的性能，特别是对于非单调子模函数或单调半可加函数的贪心最大化问题给出了近似保证，并讨论了其在最大化行列式函数、有向图上的最大割问题和组合拍卖游戏等三个实际问题中的适用性，从而为解决有界曲率的约束最大化问题的近似解提供了思路。

    Nov, 2018

  • 鲁棒的单调次模函数最大化

    研究了具有健壮性约束的基数约束单调次模函数最大化问题，提出了逼近算法，并在限制相对较小的情况下，得到了相对较好的逼近结果，并应用结果解决了更普遍的独立性约束下的最大化问题。

    Jul, 2015