Jun, 2023

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

HTML
PDF
TL;DR针对子模最大化问题，本文提出了一种动态算法，该算法对于给定序列的插入和删除操作，维护了一个在任一时间点上具有 4+ε 近似度的子系统，其参数化为 matroid 约束的秩 k，并且查找复杂度与序列长度无关；同时，我们还探讨了基于基数约束的子模最大化问题的动态算法。
发现论文，激发创造
  • 超越基数约束的弱次模最大化：贪心法是否受益于随机化？

    本文提出了一种随机贪心算法来最大化弱次模函数在一般拟阵约束下的值，其中距离次模性的距离由参数γ衡量，该算法在实践中表现良好，并且是第一个能够约束弱次模函数最大化具有非平凡逼近保证的算法。

    Jul, 2017

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

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

    Feb, 2021

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

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

    Jan, 2022

  • 非单调次模约束下背包约束下的线性查询逼近算法

    本研究提出了两种简单实用的算法逼近非单调次模最大化问题，并分析了应用于收益最大化、图像摘要、最大加权切割等三个问题的有效性。

    May, 2023

  • 基于拟阵的全动态次模最大化

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

    May, 2023

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

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

    Jul, 2023

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

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

    Aug, 2023

  • 动态非单调次模最大化

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

    Nov, 2023

  • 指导式组合算法用于次模最大化

    本研究通过开发导向测量连续贪心算法的组合类算法，实现子模函数限制下的近似比率，同时进行去随机化处理和几乎线性时间算法的开发。

    May, 2024

  • 一致子模最大化

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

    May, 2024