Jun, 2020

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

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

    研究单调子模函数下的最大值问题以及约束条件下的问题，提出了一个随机的动态算法，并给出了一个高效的数据结构来处理发生了添加和删除变化的值，该算法能够提供一个 4 近似解。

    May, 2023

  • 动态非单调次模最大化

    我们通过降低一个非单调子模函数的约束条件 k 到同样约束条件 k 下最大化一个单调子模函数，肯定回答了陈和彭提出的问题，并得到了第一个动态算法来解决非单调子模函数最大化问题。我们的算法保持了一个 (8+ε) 近似的解，并且每次更新使用预期平摊的 O (ε^-3 * k^3 * log^3 (n) * log (k)) 或者 O (ε^-1 * k^2 * log^3 (k)) 的预言查询。此外，我们展示了我们的动态算法在视频概述和基于几个真实数据集的最大割问题上的优势。

    Nov, 2023

  • 基于动态规划的拟阵子模最大化算法

    针对子模最大化问题，本文提出了一种动态算法，该算法对于给定序列的插入和删除操作，维护了一个在任一时间点上具有 4+ε 近似度的子系统，其参数化为 matroid 约束的秩 k，并且查找复杂度与序列长度无关；同时，我们还探讨了基于基数约束的子模最大化问题的动态算法。

    Jun, 2023

  • 一致子模最大化

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

    May, 2024

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

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

    Jul, 2018

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

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

    Aug, 2018

  • 基于拟阵的删除鲁棒子模型最大化

    本文研究在传统的拟阵约束下，单调子模函数的删除鲁棒版本的最大化问题，提出了空间复杂度依赖于拟阵的秩和删除元素数量的常数因子逼近算法，在中心化、流式环境下均获得了好的结果。

    Jan, 2022

  • 基于单调性不稳定的麦特罗伊德上的非单调子模最大化

    该研究探讨基于经典拟阵约束下的删除鲁棒版本的子模函数最大化问题，在此问题中，目标是提取一个小型数据集的摘要，即使在对手删除一些元素后也包含高价值独立集，该研究提供了具有常数因子逼近比的近似算法，其中空间复杂度取决于拟阵的秩 k 和已删除元素的数量 d。

    Aug, 2022

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

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

    Jul, 2020

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

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

    Jul, 2015