Non-monotone Sequential Submodular Maximization
Abstract
In this paper, we study a fundamental problem in submodular optimization known as sequential submodular maximization. The primary objective of this problem is to select and rank a sequence of items to optimize a group of submodular functions. The existing research on this problem has predominantly concentrated on the monotone setting, assuming that the submodular functions are non-decreasing. However, in various real-world scenarios, like diversity-aware recommendation systems, adding items to an existing set might negatively impact the overall utility. In response, we propose to study this problem with non-monotone submodular functions and develop approximation algorithms for both flexible and fixed length constraints, as well as a special case with identical utility functions. The empirical evaluations further validate the effectiveness of our proposed algorithms in the domain of video recommendations.
BibTeX
@article{Tang_Yuan_2024, title={Non-monotone Sequential Submodular Maximization}, volume={38}, url={https://ojs.aaai.org/index.php/AAAI/article/view/29452}, DOI={10.1609/aaai.v38i14.29452}, abstractNote={In this paper, we study a fundamental problem in submodular optimization known as sequential submodular maximization. The primary objective of this problem is to select and rank a sequence of items to optimize a group of submodular functions.
The existing research on this problem has predominantly concentrated on the monotone setting, assuming that the submodular functions are non-decreasing. However, in various real-world scenarios, like diversity-aware recommendation systems, adding items to an existing set might negatively impact the overall utility. In response, we propose to study this problem with non-monotone submodular functions and develop approximation algorithms for both flexible and fixed length constraints, as well as a special case with identical utility functions. The empirical evaluations further validate the effectiveness of our proposed algorithms in the domain of video recommendations.}, number={14}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Tang, Shaojie and Yuan, Jing}, year={2024}, month={Mar.}, pages={15284-15291} }