Enhanced deterministic approximation algorithm for non-monotone submodular maximization under knapsack constraint with linear query complexity

Canh V. Pham ()
Additional contact information
Canh V. Pham: Phenikaa University

Journal of Combinatorial Optimization, 2025, vol. 49, issue 1, No 2, 14 pages

Abstract: Abstract In this work, we consider the Submodular Maximization under Knapsack ( $$\textsf{SMK}$$ SMK ) constraint problem over the ground set of size n. The problem recently attracted a lot of attention due to its applications in various domains of combinatorial optimization, artificial intelligence, and machine learning. We improve the approximation factor of the fastest deterministic algorithm from $$6+\epsilon $$ 6 + ϵ to $$5+\epsilon $$ 5 + ϵ while keeping the best query complexity of O(n), where $$\epsilon >0$$ ϵ > 0 is a constant parameter. Our technique is based on optimizing the performance of two components: the threshold greedy subroutine and the building of two disjoint sets as candidate solutions. Besides, by carefully analyzing the cost of candidate solutions, we obtain a tighter approximation factor.

Keywords: Submodular maximization; Knapsack constraint; Approximation algorithm; Query complexity (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01232-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:49:y:2025:i:1:d:10.1007_s10878-024-01232-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01232-9

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().