May, 2024

满足基数约束下的亚模模极大化的实用 0.385 近似

PDF
TL;DR我们提出了一种新的算法，可以在实践中有效地解决非单调受限子模型最大化问题，结合了 0.385 的逼近保证和低的查询复杂度。通过在各种机器学习应用中进行实验，包括电影推荐、图像摘要等，我们评估了我们算法的实验性能，证明了我们方法的功效。
non-monotone constrained submodular maximizationapproximation algorithmcomputational complexitypractical algorithmsempirical performance
发现论文，激发创造
  • 具近似最优适应性和查询复杂度的非单调次模最大化

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

    Aug, 2018

  • 噪音下的次模优化

    本文考虑在噪声下最大化单调子模函数，探讨在噪声和误差存在的情况下，是否能获得算法的可证明保证，结论是对于基数约束 k>=2 的函数，有一个近似算法，其近似比例任意接近 1-1/e; 对于基数约束 k=1，有一种算法，其近似比率任意接近于 1/2。没有随机算法可以获得比 1/2+o (1) 更好的近似度；如果噪声是对抗性的，则不能获得任何非平凡的近似保证。

    Jan, 2016

  • 非单调次模最大化的实用并行算法

    非单调子模最大化问题和打包约束下的子模并行算法设计优化和逼近

    Aug, 2023

  • 动态非单调次模最大化

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

    Nov, 2023

  • 具有近似最优的适应性和查询复杂度的子模最大化

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

    Jul, 2018

  • 近似最优化的子模最大化算法及其近线性时间自适应实现

    本文研究了在满足基数约束的条件下，最大化单调子模函数的逼近保证和适应性之间的权衡问题。我们给出了第一个使用 O（lnn /epsilon^2）轮适应性实现 1-1 /e-epsilon 逼近的算法，同时算法的函数评估次数和额外运行时间分别为 O（npoly（logn，1 /epsilon））。

    Apr, 2018

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

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

    Jul, 2020

  • 可适应近最优复杂度的组合算法：在背包约束条件下子模块最大化

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

    Feb, 2021

  • 子模最大化的指数级并行运行时间加速，无需牺牲近似度

    本文探讨了子模最大化算法的适应性，证明了一个新的算法可以在 O (log n) 自适应回合内实现接近于最优 1-1/e 近似。

    Apr, 2018

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

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

    Jun, 2017