Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint

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.