AAAINov, 2018

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

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

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

    Mar, 2017

  • 受限曲率下次模优化和超模优化的最优逼近

    论文设计了一种新的逼近算法来解决在单一拟阵约束下优化子模和超模函数的问题，特别地，当目标函数有闭合总曲率时，获得了一个 (1-c/e)- 近似的结果；该算法基于连续贪心算法和非随机局部搜索的修改，并进行了扩展以包括在一些特定场景下的应用，例如最大熵抽样和列子集选择问题。

    Nov, 2013

  • 满足拟阵和背包约束的非单调次模最大化

    本文提出了第一个常因子近似算法来实现任何非负子模函数的最大化，同时满足多个基数约束或背包约束，特别是在 k 个划分拟阵约束下，改进了以前已知的最佳保证，获得了（1 /k+1 + 1 /k-1 + ε）的近似保证。

    Feb, 2009

  • 并行下考虑拟阵约束和装箱限制的子模块最大化

    本文提出了一种在单个 matroid 约束或多个 packing 约束下，通过小量自适应查询轮次来最大化 submodular 函数的多线性扩展的算法，该算法在 submodular maximization with a matroid constraint 和 non-monotone submodular maximization subject to packing constraints 两个问题上均获得了近乎最佳的拟合比例，并且在自适应轮次和并行运行时间上提出了指数级别的加速。

    Aug, 2018

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

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

    Feb, 2020

  • 子模最大化问题的紧凑组合算法在矩阵约束条件下的应用

    提出了一种基于组合数学的算法，用于求解在一个制约性匹配中的单调子模优化问题，算法具有很高的精度和时间效率。

    Apr, 2012

  • 在背包约束下最大化有界曲率的单调次模函数

    提出一种用于最大化满足背包限制下单调子模函数的算法，并且该算法的多项式时间复杂度为一个取决于输入函数曲率 c 的比率，该算法的近似度为 1-c/e-ε，这一近似度对于任何处于区间 [0,1] 中的 c 值均是紧确的。此外，该研究提供了用于预算分配问题的多项式时间算法，并且有一种更好的近似度。

    Jul, 2016

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

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

    Jul, 2017

  • 通过多项式估计进行随机子模最大化

    本研究以连续贪心算法为基础，研究了具有一般性骨架约束的随机子模最大化问题，主要应用于在线学习，团队形成，设施位置，影响最大化，主动学习和感知目标函数。实验表明，使用多项式梯度估计代替样本估计，可有效减少随机性并缩短执行时间。

    Mar, 2023

  • 分布式子模最大化

    本文提出了一种适用于分布式计算的子模函数最大化方法 GreeDi，该方法可在 MapReduce 框架下实现，初步实验表明该方法可应用于大规模机器学习任务中的子模优化问题，如稀疏高斯过程推断和样例聚类等问题，且在一定的自然条件下，可以达到接近于传统集中式计算模式下的性能表现。

    Nov, 2014