Apr, 2018

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

PDF
TL;DR本文探讨了子模最大化算法的适应性，证明了一个新的算法可以在 O (log n) 自适应回合内实现接近于最优 1-1/e 近似。
submodular maximizationadaptivitygreedy algorithmapproximationpolynomial-time algorithms
发现论文，激发创造
  • 近似最优化的子模最大化算法及其近线性时间自适应实现

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

    Apr, 2018

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

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

    Jul, 2018

  • 具近似最优适应性和查询复杂度的非单调次模最大化

    研究分布式情况下近似最大化非单调子模函数时算法适应性和查询复杂度的方法及其应用

    Aug, 2018

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

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

    Aug, 2023

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

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

    Jul, 2018

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

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

    Feb, 2021

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

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

    Aug, 2018

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

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

    Nov, 2019

  • 子模量极大化的 FAST 算法

    本篇论文介绍了一种新算法 FAST，旨在通过最大化满足劣模性的子模函数，使逼近比例任意接近 1-1 /e，由 O (log（n）log^2 (log k)) 次适应，总共使用 O（nloglog (k)) 次查询，在处理大数据集方面，该算法的查询复杂度和轮数都非常高效，且实验证明，FAST 比最先进的串行算法甚至是并行化的经过超级优化的状态算法都快得多。

    Jul, 2019

  • 针对背包约束的快速自适应非单调子模型最大化

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

    Jul, 2020