本文提出了一种随机贪心算法来最大化弱次模函数在一般拟阵约束下的值,其中距离次模性的距离由参数γ衡量,该算法在实践中表现良好,并且是第一个能够约束弱次模函数最大化具有非平凡逼近保证的算法。
Jul, 2017
针对拥有大规模实例的问题,本文提出了第一个自适应复杂度为 O(log n),且求解非单调子模问题的背包约束问题的常数因子逼近算法,该算法提出了一个子线性适应性的组合方法,其查询值仅为O(n)。
Feb, 2021
本文研究在传统的拟阵约束下,单调子模函数的删除鲁棒版本的最大化问题,提出了空间复杂度依赖于拟阵的秩和删除元素数量的常数因子逼近算法,在中心化、流式环境下均获得了好的结果。
Jan, 2022
该研究探讨基于经典拟阵约束下的删除鲁棒版本的子模函数最大化问题,在此问题中,目标是提取一个小型数据集的摘要,即使在对手删除一些元素后也包含高价值独立集,该研究提供了具有常数因子逼近比的近似算法,其中空间复杂度取决于拟阵的秩k和已删除元素的数量d。
Aug, 2022
本研究提出了两种简单实用的算法逼近非单调次模最大化问题,并分析了应用于收益最大化、图像摘要、最大加权切割等三个问题的有效性。
May, 2023
研究单调子模函数下的最大值问题以及约束条件下的问题,提出了一个随机的动态算法,并给出了一个高效的数据结构来处理发生了添加和删除变化的值,该算法能够提供一个4近似解。
针对子模最大化问题,本文提出了一种动态算法,该算法对于给定序列的插入和删除操作,维护了一个在任一时间点上具有 4+ε 近似度的子系统,其参数化为 matroid 约束的秩 k,并且查找复杂度与序列长度无关;同时,我们还探讨了基于基数约束的子模最大化问题的动态算法。
Jun, 2023
非单调子模最大化问题和打包约束下的子模并行算法设计优化和逼近
Aug, 2023
本研究通过开发导向测量连续贪心算法的组合类算法,实现子模函数限制下的近似比率,同时进行去随机化处理和几乎线性时间算法的开发。
May, 2024
在本研究中,我们考虑了基于背包约束的子模型最大化问题,该问题涉及大小为n的总体。我们将最快确定性算法的近似因子从6+ε改进为5+ε,同时保持了O(n)的最佳查询复杂度。我们的技术是基于两个组件的性能优化:阈值贪婪子程序和建立两个不相交集合作为候选解。此外,通过仔细分析候选解的成本,我们获得了更紧的近似因子。