Aug, 2018

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

PDF
TL;DR本文提出了一种在单个 matroid 约束或多个 packing 约束下，通过小量自适应查询轮次来最大化 submodular 函数的多线性扩展的算法，该算法在 submodular maximization with a matroid constraint 和 non-monotone submodular maximization subject to packing constraints 两个问题上均获得了近乎最佳的拟合比例，并且在自适应轮次和并行运行时间上提出了指数级别的加速。
adaptive roundssubmodular maximizationmatroid constraintparallel algorithmdiminishing returns submodular
发现论文，激发创造
  • 满足拟阵和背包约束的非单调次模最大化

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

    Feb, 2009

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

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

    Jul, 2018

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

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

    Apr, 2012

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

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

    Aug, 2023

  • 基于拟阵约束的 k 次次模最大化的快速算法

    应用阈值减小算法最大化满足 matroid 约束的 k - 次模函数，提出逼近算法来最大化满足单调和非单调 k - 次模函数，并提供了关于时间复杂度的结果，同时还介绍了针对总大小约束的快速算法。

    Jul, 2023

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

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

    Jul, 2010

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

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

    Nov, 2013

  • 通过多线性松弛和竞争解决方案的子模函数最大化

    研究了如何在不同的 packing 类型约束下，最大化定义在给定集合上的非负子模函数，提出了一个基于多线性扩展和分数解取整的算法框架，并且解决了其中的一些重要限制问题，开辟了线性和子模函数最大化的新方法。

    May, 2011

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

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

    Apr, 2018

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

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

    Jan, 2011