# Metadata

- Title: Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint
- Authors: Canh V. Pham, Tan D. Tran, Dung T. K. Ha, My T. Thai
- Year: 2023
- Venue: Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI 2023)
- Primary group: submodular
- Secondary tags: non-monotone, knapsack, linear-query, deterministic, randomized, thresholding
- Problem: non-monotone submodular maximization under a single knapsack constraint with emphasis on reducing oracle-query complexity
- Main guarantee: introduces a deterministic algorithm DLA with approximation factor 6 + epsilon and a randomized algorithm RLA with approximation factor 4 + epsilon, both within O(n log(1/epsilon) / epsilon) query complexity
- Key techniques: linear-query coarse approximation via ground-set splitting, threshold greedy over disjoint candidate sets, randomized rescanning to improve deterministic baseline
- Status: processed-deep
- Tags: #submodular #non-monotone #knapsack #linear-query #thresholding #randomized
- Inbox source: inbox/1. SMK23.pdf