Nov, 2013

带有子模块覆盖和子模块背包约束的子模块优化

HTML
PDF
TL;DR本文研究两个新的优化问题——在满足子模下限的约束条件下最小化子模函数（子模覆盖）和在满足子模上限的约束条件下最大化子模函数（子模背包）。我们将这些问题表述为约束优化问题，并获得许多有界逼近保证。此外，我们证明了这两个问题的紧密关联，并提供了一种解决一个问题的逼近算法用于获得另一个问题的逼近保证。最后，我们通过实验证明了本文算法的效果和良好的可扩展性。
发现论文，激发创造
  • 子模函数学习：凸优化观点

    本文从凸分析的角度介绍了子模函数，论述了子模函数最小化与各类凸优化问题的关系，提出了新的高效算法以及多种子模函数在机器学习中的应用。

    Nov, 2011

  • 近似最小化次模函数差的算法及应用

    本研究扩展了Narasimhan和Bilmes的工作，提出了基于子模函数差别最小化的新算法，该算法能有效地解决多种组合约束的问题，并且能够用于许多机器学习问题中，它在性能上优于现有的算法。

    Jul, 2012

  • 学习和最小化子模函数的曲率和最优算法

    本文探究了三个相关且重要的机器学习问题。我们展示了这三个问题的复杂度都依赖于子模函数的'曲率'，并提供了改进旧有结果的上下界。我们证明了曲率对于子模函数的近似、最小化和学习有影响，并通过实验结果支持了我们的理论结论。

    Nov, 2013

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

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

    Jul, 2017

  • 随机子模极大化：覆盖函数的情形

    该论文研究了如何将随机梯度下降等连续优化算法应用到离散问题中的子模优化，通过将扩展线性化处理并通过向上投影处理，得到离散解，针对加权覆盖函数进行研究，实验表明，该方法在保证最优近似率的同时，大幅降低了计算成本。

    Nov, 2017

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

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

    Feb, 2021

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

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

    Aug, 2023

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

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

    Sep, 2023

  • 优化具有变量不确定性的概率约束子模问题

    本文研究了确定性设定中的概率约束子模优化问题，提出了一种新的分析方法，并提供了贪心算法来近似求解最优解。在实验中，演示了算法在几个最大覆盖问题和影响力最大化问题上的有效性。

    Sep, 2023

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

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

    May, 2024