Sep, 2024

非单调子模极大化的改进并行算法及其背包约束

HTML
PDF
TL;DR本研究针对在背包约束下非单调子模极大化问题，提出了一种高效的并行算法，有效将现有并行算法的最佳近似因子从$8+\epsilon$提高到$7+\epsilon$，且具备$O(\log n)$的自适应复杂度。通过构建新的交替阈值算法框架，该算法在保证自适应复杂度的同时显著提升了解的质量，在收入最大化、图像摘要和最大加权切割等多个应用上进行了广泛的实验研究，展现出优越的性能。
发现论文，激发创造
  • 针对背包约束的快速自适应非单调子模型最大化

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

    Jul, 2020

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

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

    Feb, 2021

  • 非单调次模约束下背包约束下的线性查询逼近算法

    本研究提出了两种简单实用的算法逼近非单调次模最大化问题，并分析了应用于收益最大化、图像摘要、最大加权切割等三个问题的有效性。

    May, 2023

  • 约束k次模最大化的在线和流式算法

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

    May, 2023

  • 基于交集副模块的最大化问题在玩偶集和背包约束下的求解

    本文研究了在多种约束条件下的子模最大化问题，并提出了SPROUT算法和SPROUT++算法，证明它们能够比现有算法更好地实现多项式近似保证，并通过电影推荐和加权最大切割等应用的实验证明了SPROUT++算法的优越性。

    Jul, 2023

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

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

    Aug, 2023

  • 非单调$k$-次模最大化问题的鲁棒近似算法在背包约束下

    提出了两个确定性近似算法来解决非单调k-次模极大化问题，其在查询复杂度仅为O(nk)的情况下提供了常数近似比率，比现有算法少使用了Omega(log n)数量的查询。

    Sep, 2023

  • 动态非单调次模最大化

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

    Nov, 2023

  • 非单调子模型最大化在线性查询复杂度下的增强确定性近似算法

    在本研究中，我们考虑了基于背包约束的子模型最大化问题，该问题涉及大小为n的总体。我们将最快确定性算法的近似因子从6+ε改进为5+ε，同时保持了O(n)的最佳查询复杂度。我们的技术是基于两个组件的性能优化：阈值贪婪子程序和建立两个不相交集合作为候选解。此外，通过仔细分析候选解的成本，我们获得了更紧的近似因子。

    May, 2024

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

    我们提出了一种新的算法，可以在实践中有效地解决非单调受限子模型最大化问题，结合了0.385的逼近保证和低的查询复杂度。通过在各种机器学习应用中进行实验，包括电影推荐、图像摘要等，我们评估了我们算法的实验性能，证明了我们方法的功效。

    May, 2024