Efficient Algorithms for Monotone Non-Submodular Maximization with Partition Matroid Constraint
Abstract
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.
Cite
Text
Nguyen and Thai. "Efficient Algorithms for Monotone Non-Submodular Maximization with Partition Matroid Constraint." International Joint Conference on Artificial Intelligence, 2022. doi:10.24963/IJCAI.2022/666Markdown
[Nguyen and Thai. "Efficient Algorithms for Monotone Non-Submodular Maximization with Partition Matroid Constraint." International Joint Conference on Artificial Intelligence, 2022.](https://mlanthology.org/ijcai/2022/nguyen2022ijcai-efficient/) doi:10.24963/IJCAI.2022/666BibTeX
@inproceedings{nguyen2022ijcai-efficient,
title = {{Efficient Algorithms for Monotone Non-Submodular Maximization with Partition Matroid Constraint}},
author = {Nguyen, Lan N. and Thai, My T.},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2022},
pages = {4807-4813},
doi = {10.24963/IJCAI.2022/666},
url = {https://mlanthology.org/ijcai/2022/nguyen2022ijcai-efficient/}
}