提出两种高效算法，解决带大小约束的非单调DR-子模最大化问题。
Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint
- 设计两类快速近似算法，查询复杂度仅O(n log k)
- 最快算法达0.044逼近比，另一算法接近1/4
- 适合需低查询开销的优化场景，如收益最大化
本文研究在包含n个元素的基集上，满足大小约束k的非单调DR-子模最大化问题。提出两种近似算法：FastDrSub和FastDrSub++。FastDrSub实现0.044的逼近比，查询复杂度为O(n log k)；FastDrSub++在参数ε>0下达到1/4−ε的逼近比，查询复杂度同样为O(n log k)。二者均为首个在低复杂度O(n log k)下实现常数逼近比的算法。实验评估显示，所提算法在收益最大化任务中显著优于现有方法，兼具更低查询次数与更优解质量。
原文摘要 · Abstract (English)
This work studies the non-monotone DR-submodular Maximization over a ground set of $n$ subject to a size constraint $k$. We propose two approximation algorithms for solving this problem named FastDrSub and FastDrSub++. FastDrSub offers an approximation ratio of $0.044$ with query complexity of $O(n \log(k))$. The second one, FastDrSub++, improves upon it with a ratio of $1/4-ε$ within query complexity of $(n \log k)$ for an input parameter $ε>0$. Therefore, our proposed algorithms are the first constant-ratio approximation algorithms for the problem with the low complexity of $O(n \log(k))$. Additionally, both algorithms are experimentally evaluated and compared against existing state-of-the-art methods, demonstrating their effectiveness in solving the Revenue Maximization problem with DR-submodular objective function. The experimental results show that our proposed algorithms significantly outperform existing approaches in terms of both query complexity and solution quality.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。