# Metadata

- Title: Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint
- Authors: Tan D. Tran, Canh V. Pham, Dung T. K. Ha, Phuong N. H. Pham
- Year: 2024
- Venue: Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI 2024)
- Primary group: submodular
- Secondary tags: non-monotone, knapsack, parallel, adaptivity, thresholding
- Problem: non-monotone submodular maximization under a knapsack constraint in the low-adaptivity / parallel oracle model
- Main guarantee: introduces AST, a (7 + epsilon)-approximation algorithm with O(log n) adaptivity and near-linear query complexity O~(nk)
- Key techniques: alternate-threshold framework, parallel threshold sampling, adaptive density thresholds, two disjoint candidate solutions
- Status: processed-deep
- Tags: #submodular #non-monotone #knapsack #parallel #adaptivity #thresholding
- Inbox source: inbox/4. SMK24.pdf