.png){kind=icon}
.png){kind=icon}
Return
Fast approximation algorithm for non-monotone DR-submodular maximization under size constraint
.png){kind=icon}
PRE
AI
DOI：10.1007/s10878-025-01374-4.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 - is an element of within query complexity of (n log k) for an input parameter is an element of > 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
Keywords:
Approximation algorithm
Submodular
DR-submodular
Integer lattice
Size constraint
Journal
J
IF:
1.1
Papers:
78
Citations:
0
Organization
No organization information available