Efficient Algorithms for Monotone Non-Submodular Maximization with Partition Matroid Constraint

Efficient Algorithms for Monotone Non-Submodular Maximization with Partition Matroid Constraint

Lan N. Nguyen, My T. Thai

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
Main Track. Pages 4807-4813. https://doi.org/10.24963/ijcai.2022/666

In this work, we study the problem of monotone non-submodular maximization with partition matroid constraint. Although a generalization of this problem has been studied in literature, our work focuses on leveraging properties of partition matroid constraint to (1) propose algorithms with theoretical bound and efficient query complexity; and (2) provide better analysis on theoretical performance guarantee of some existing techniques. We further investigate those algorithms' performance in two applications: Boosting Influence Spread and Video Summarization. Experiments show our algorithms return comparative results to the state-of-the-art algorithms while taking much fewer queries.
Keywords:
Search: Combinatorial Search and Optimisation