← Search

Phuong N. H. Pham

2 accepted papers

2024

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

IJCAI 2024poster

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 ke…

Cited by 0SourcePDFScholar