Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint

Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint

Tan D. Tran, Canh V. Pham, Dung T. K. Ha, Phuong N. H. Pham

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence
Main Track. Pages 1961-1969. https://doi.org/10.24963/ijcai.2024/217

This work proposes an efficient parallel algorithm for non-monotone submodular maximization under a knapsack constraint problem over the ground set of size n. Our algorithm improves the best approximation factor of the existing parallel one from 8 to 7 with O(log n) adaptive complexity. The key idea of our approach is to create an alternate threshold algorithmic framework. This new strategy alternately constructs two disjoint candidate solutions within a constant number of sequence rounds. Then, the algorithm boosts solution quality without sacrificing the adaptive complexity. Extensive experimental studies on three applications, Revenue Maximization, Image Summarization, and Maximum Weighted Cut, show that our algorithm not only significantly increases solution quality but also requires comparative adaptivity to state-of-the-art algorithms.
Keywords:
Constraint Satisfaction and Optimization: CSO: Constraint optimization problems
Constraint Satisfaction and Optimization: CSO: Applications
Constraint Satisfaction and Optimization: CSO: Constraint learning and acquisition
Data Mining: DM: Big data and scalability