Aug, 2016

约束子模最大化问题：超越 1/e

PDF
TL;DR本研究提出了一种新的算法，用于在普遍限制条件下最大化非单调子模函数。该算法在下闭多面体上找到了一个函数的多线性扩展的近似分数解，其近似保证是 0.372，这是在 1/e 近似之上的首次改进，由连续贪心算法 [Feldman 等，FOCS2011] 实现。
发现论文，激发创造
  • 并行下考虑拟阵约束和装箱限制的子模块最大化

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

    Aug, 2018

  • 模拟退火算法进行子模最大化

    提出一种基于模拟退火的新算法用于解决子模块最大化问题，证明该算法支持两种问题的改进近似，在数值预言模型中，子模块最大化问题在独立约束和基约束条件下都不可能有更好的解决方案。

    Jul, 2010

  • 具背包约束的单调和非单调次模最大化的近似算法

    本文讨论了带有 $d$ 背包限制的任意模子模函数最大化问题，建立了离散问题和连续松弛之间的强联系，并利用这种联系提出了近似算法和确定性技术，得到了很好的解决方案。

    Jan, 2011

  • 基于多线性松弛的子模函数并行最大化

    提出一种并行算法，近似地解决了一个具有约束的子模函数的多线性松弛问题，结果在很多约束条件下都得到有效解决。

    Jul, 2018

  • 在线非单调 DR 子模最大化

    本文研究了 DR - 次模连续函数在最大化过程中的基本问题，并在凸集合的不同类型下提出了一系列在线算法，用于最小化在线非单调 DR - 次模函数。在实验中表现良好并为机器学习领域中有关问题提供了新的解决方案。

    Sep, 2019

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

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

    Apr, 2012

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

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

    Feb, 2009

  • 小批量次模最大化

    我们提出了第一个用于最大化非负单调可分解次模函数的小批量算法，在一组约束条件下。我们在理论和实践上都优于基于稀疏化方法的方法。我们在实验中观察到，我们的算法生成的解比基于稀疏化方法生成的解要好得多。

    Jan, 2024

  • 鲁棒的单调次模函数最大化

    研究了具有健壮性约束的基数约束单调次模函数最大化问题，提出了逼近算法，并在限制相对较小的情况下，得到了相对较好的逼近结果，并应用结果解决了更普遍的独立性约束下的最大化问题。

    Jul, 2015

  • 通过非对称技术来实现受限子模最大化

    本文研究了带有子模性目标函数的组合优化问题，提出了一种基于新技术的算法来优化多线性松弛问题，该算法避免了对称性等性质的需要，适用于约束问题，相比之前的算法，它具有更好的保证。

    Nov, 2016