{"ID":2846059,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.02254","arxiv_id":"2511.02254","title":"Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint","abstract":"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 $ε\u003e0$. 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.","short_abstract":"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 secon...","url_abs":"https://arxiv.org/abs/2511.02254","url_pdf":"https://arxiv.org/pdf/2511.02254v1","authors":"[\"Tan D. Tran\",\"Canh V. Pham\"]","published":"2025-11-04T04:37:16Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.AI\",\"cs.CC\"]","methods":"[]","has_code":false}