非单调 $k$- 次模最大化问题的鲁棒近似算法在背包约束下

Sep, 2023

非单调 $k$- 次模最大化问题的鲁棒近似算法在背包约束下

Robust Approximation Algorithms for Non-monotone $k$-Submodular Maximization under a Knapsack Constraint

Dung T.K. Ha, Canh V. Pham, Tan D. Tran, Huan X. Hoang

TL;DR提出了两个确定性近似算法来解决非单调 k - 次模极大化问题，其在查询复杂度仅为 O (nk) 的情况下提供了常数近似比率，比现有算法少使用了 Omega (log n) 数量的查询。

Abstract

The problem of non-monotone $k$-submodular maximization under a knapsack constraint ($\kSMK$) over the ground set size $n$ has been raised in many applications in machine learning, such as data summarization, information propagation, etc. However, existing algorithms for the problem ar

non-monotone k-submodular maximization knapsack constraint deterministic approximation algorithms query complexity

发现论文，激发创造

非单调子模型最大化在线性查询复杂度下的增强确定性近似算法

在本研究中，我们考虑了基于背包约束的子模型最大化问题，该问题涉及大小为 n 的总体。我们将最快确定性算法的近似因子从 6+ε 改进为 5+ε，同时保持了 O (n) 的最佳查询复杂度。我们的技术是基于两个组件的性能优化：阈值贪婪子程序和建立两个不相交集合作为候选解。此外，通过仔细分析候选解的成本，我们获得了更紧的近似因子。

May, 2024

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

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

May, 2023

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

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

Jul, 2020

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

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

Aug, 2023

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

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

Jan, 2011

满足背包约束的敌对鲁棒次模最大化

该研究提出了针对单个和多个背包约束下的单调次模最大化的首个对抗鲁棒算法，具有可扩展的分布式和流式实现。性能评估结果表明，与现有非鲁棒算法的自然鲁棒化相比，该算法对于大型社交网络图等输入具有最佳的目标结果，并表现出极强的性能，即使与提前给出拆除集合的线下算法相比也是如此。

May, 2019

满足拟阵和背包约束的非单调次模最大化

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

Feb, 2009

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

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

Feb, 2021

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

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

Aug, 2018

鲁棒子模最大化：一种非均匀划分方法

本文研究了在确定性的 $ au$ 时，如何在满足固定大小约束 $k$ 的条件下最大化单调子模函数。提出了新的分区鲁棒性子模最大化算法，其构造具有指数增加大小的桶的分区，并在桶上应用标准子模优化子例程，证明了我们的算法对于更一般的 $ au = o（k）$ 具有相同的保证。在数据汇总和影响最大化方面，数值上验证了 PRo 的性能，并展示了对贪婪算法和 Orlin 等人的算法的优势。

Jun, 2017