Dung T. K. Ha

Efficient Parallel Algorithms with Linear Queries for Non-Monotone Submodular Maximization

In this work, we propose the first constant-approximation algorithms, LinAst and LinAtg, which simultaneously achieve optimal query complexity O(n) and adaptive complexity O(log n) for non-monotone submodular maximization under a cardinality constraint k over a ground set of size n. Specifically, compared with existing...