Jan, 2015

在线子模最大化算法及其中断

PDF
TL;DR本文研究基于在线变体的子模函数最大化问题，探讨了两种特殊情况并得出了竞争比的上下界。具体而言，设计了一个 $1/e$ 竞争算法和一个针对最多只包含 k 个元素的解的常数竞争比算法。
submodular function maximizationonline variantcompetitive ratioupper and lower boundselement selection
发现论文，激发创造
  • 在线玄学最大化下的基合约束与学习分配应用

    本文提出了一种能够动态地为信息源进行排序，同时又能保证重复信息的减少不会影响子模函数的最优化问题算法，并在真实的 Web 数据集中分别实验了广告分配和动态排名两个在线优化问题。

    Jul, 2014

  • 一致子模最大化

    在具有一致性约束的动态环境中，我们研究了在基数约束下最大化单调次模函数，其在数据挖掘和机器学习中有多个应用。我们提供了在此场景中具有一致性和逼近质量之间不同权衡的算法。实验证明我们算法在真实世界实例中的有效性。

    May, 2024

  • 快速子模函数最大化

    本研究提出了一种基于新型搜索树数据结构的算法，可以高效地计算在线和离线子模函数最大值问题。

    May, 2023

  • 约束 k 次模最大化的在线和流式算法

    本文提出了单遍流式和在线算法的受约束 k - 次模最大化，其中包含基数和背包约束限制，该算法可以提供不错的近似解和高效的解决方案，并在广告分配等应用实例上得到了验证。

    May, 2023

  • 结构稳健次模最大化：离线与在线算法

    本文提出了鲁棒次模函数最大化及其在结构组合约束下的有效算法，旨在提高对次模优化的建模范围，尤其应用于单个或多个基序，背包以及具有分散鲁棒性的标准约束条件，该算法适用于离线和在线设置，并且在线问题的双标准解决方案具有 sub-linear 的遗憾。

    Oct, 2017

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

    本研究提出了一种新的算法，用于在普遍限制条件下最大化非单调子模函数。该算法在下闭多面体上找到了一个函数的多线性扩展的近似分数解，其近似保证是 0.372，这是在 1/e 近似之上的首次改进，由连续贪心算法 [Feldman 等，FOCS2011] 实现。

    Aug, 2016

  • 在线自由处理子模最大化：随机化对分割矩阵 0.25 优势

    本文研究了带有破坏性（free disposal）的 matroid 约束下的在线次模最大化问题。针对 k-uniform matroids，本文提出了一个与以往最优算法竞争比例更高的确定性算法；同时，本文也探讨了在 partition matroids 约束下确定性算法的下限，及随机算法的优势。

    Oct, 2016

  • 通过随机化实现子模函数最大化的长期公平性

    通过开发近似算法解决具有组内公平性约束的单调子模函数最大化问题。

    Apr, 2023

  • 流式自适应次模最大化

    本文介绍了一种新的半策略次模函数类，针对流式问题，开发了一系列有效的算法来最大化其性能。

    Aug, 2022

  • 约束次模优化问题的全动态算法

    本研究在完全动态的环境下，旨在最大化基数约束下的单调子模函数，研究结果为一个具有多项式对数的摊销更新时间和可得到 0.5-ε 近似解的随机算法，并结合经验研究证明了算法性能的优越性。

    Jun, 2020