Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint
Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint
复制标题
DOI：
10.48550/arxiv.2305.10292
复制
发表时间：
2023-05
期刊：
影响因子：
--
通讯作者：
Canh V. Pham;Tan D. Tran;Dung T. K. Ha;M. Thai
中科院分区：
文献类型：
--
作者：
Canh V. Pham;Tan D. Tran;Dung T. K. Ha;M. Thai
本文首次提出了在背包约束下n阶基集合上非单调子模最大化的两种具有线性查询复杂度的恒因子近似算法DLA和RLA。DLA是一种确定性算法，其近似因子接近6，而RLA是一种随机化算法，其近似因子接近4。两者都运行在线性查询复杂性中。线性查询获得恒定逼近比的关键思想在于：(1)将基本集合划分为两个合适的子集，以在这些子集上找到线性查询的次优解；(2)将阈值贪婪与两个不相交集合的性质或随机选择过程相结合，以提高解的质量。除了理论分析外，我们还通过三个应用程序对我们提出的解决方案进行了评估：收益最大化、图像摘要和最大加权切割，结果表明，我们的算法不仅将比较结果返回给最先进的算法，而且需要的查询大大减少。
This work, for the first time, introduces two constant factor approximation algorithms with linear query complexity for non-monotone submodular maximization over a ground set of size n subject to a knapsack constraint, DLA and RLA. DLA is a deterministic algorithm that provides an approximation factor of nearly 6 while RLA is a randomized algorithm with an approximation factor of nearly 4. Both run in linear query complexity. The key idea to obtain a constant approximation ratio with linear query lies in: (1) dividing the ground set into two appropriate subsets to find the near-optimal solution over these subsets with linear queries, and (2) combining a threshold greedy with properties of two disjoint sets or a random selection process to improve solution quality. In addition to the theoretical analysis, we have evaluated our proposed solutions with three applications: Revenue Maximization, Image Summarization, and Maximum Weighted Cut, showing that our algorithms not only return comparative results to state-of-the-art algorithms but also require significantly fewer queries.