Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity
This work provides an incremental improvement for researchers in combinatorial optimization and AI, addressing a specific bottleneck in submodular maximization algorithms.
The paper tackles the Submodular Maximization under Knapsack constraint problem by improving the approximation factor of the fastest deterministic algorithm from 6+ε to 5+ε while maintaining linear query complexity of O(n).
In this work, we consider the Submodular Maximization under Knapsack (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 combination optimization, artificial intelligence, and machine learning. We improve the approximation factor of the fastest deterministic algorithm from $6+ε$ to $5+ε$ while keeping the best query complexity of $O(n)$, where $ε>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.