Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity
<|reference_start|>Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity: 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+\epsilon$ to $5+\epsilon$ while keeping the best query complexity of $O(n)$, where $\epsilon >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.<|reference_end|>
@article{pham2024enhanced,
    title={Enhanced Deterministic Approximation Algorithm for Non-monotone
  Submodular Maximization under Knapsack Constraint with Linear Query
  Complexity},
    author={Canh V. Pham},
    journal={arXiv preprint arXiv:2405.12252},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.12252},
    primaryClass={cs.DS cs.AI}
}