May, 2024

自适应次模覆盖问题的贪婪近似比的下界

PDF
TL;DR贪婪算法的自适应子模块覆盖近似比率至少为 1.3 *（1 + ln Q），这篇论文否定了 Golovin-Krause 在 `` 自适应子模块性：主动学习和随机优化的新方法 '' 中宣称相同算法具有（1 + ln Q）^2 近似比率的先前结果。
greedy algorithmadaptive-submodular coverapproximation ratioadaptive submodularityactive learning
发现论文，激发创造
  • 最坏情况下的自适应亚模模糊覆盖

    本文研究自适应子模块覆盖问题，在最坏情况下进行研究。该问题推广了许多以前研究过的问题，对于固定成本下观察每个医学测试的结果的效用函数，我们目的是选择一组物品以实现 “目标值”，并在最小化实现代价（最大较差情况下成本）的同时逐步选择这些物品。同时研究了最坏情况下的最大覆盖问题。

    Oct, 2022

  • 指导式组合算法用于次模最大化

    本研究通过开发导向测量连续贪心算法的组合类算法，实现子模函数限制下的近似比率，同时进行去随机化处理和几乎线性时间算法的开发。

    May, 2024

  • 交互式次模集覆盖

    本文提出一种新的交互子模集覆盖问题，探讨了其在社交网络广告、有限假设类别的有误学习中的应用，给出了一种基于贪心算法的近似保证，并且证明了逼近难度。同时分享了早期实验结果。

    Feb, 2010

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

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

    Apr, 2018

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

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

    Apr, 2018

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

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

    Jul, 2018

  • 自适应组合最大化：超过近似贪心策略

    我们研究了自适应组合最大化问题，在机器学习中是一个核心挑战，并应用于主动学习以及其他许多领域。我们研究贝叶斯设置下，考虑最大化目标在基数约束和最小成本覆盖下。我们提供了新的综合近似保证，包括之前的结果，并且更加加强了它们。我们的近似保证同时支持最大增益比以及接近次模效用函数，包括了在基数约束和最小成本覆盖下的最大化保证。此外，我们对一种修改后的先验提供了近似保证，这对于获得独立于先验最小概率的主动学习保证至关重要。此外，我们发现了一种自适应选择策略的新参数，称之为 “最大增益比”。我们展示了这个参数比之前近似保证中使用的贪婪近似参数要更加宽松，并展示了它可以提供比之前结果更强的近似保证。特别地，我们展示了最大增益比永远不会大于策略的贪婪近似因子，并且它可以大为缩小。这为自适应组合最大化中有用的策略特性提供了新的见解。

    Apr, 2024

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

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

    Feb, 2020

  • 自适应子模性中的适应性

    本文提出了半自适应策略，用于最大化自适应单调次模函数，能够实现几乎完美的近似保证，并将自适应次模最大化策略的适应性差距缩小了指数级别。

    Nov, 2019

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

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

    May, 2023