Budgeted Sequence Submodular Maximization

Chen, Xuefeng, Feng, Liang, Cao, Xin, Zeng, Yifeng and Hou, Yaqing (2022) Budgeted Sequence Submodular Maximization. In: Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence. Proceedings of the International Joint Conference on Artificial Intelligence . International Joint Conferences on Artificial Intelligence, Darmstadt, Germany, pp. 4733-4739. ISBN 9781956792003

Preview	Text 0656.pdf - Published Version Download (511kB) | Preview
Preview	Text BSSM_IJCAI_Cam.pdf - Accepted Version Download (400kB) | Preview

Abstract

The problem of selecting a sequence of items that maximizes a given submodular function appears in many real-world applications. Existing study on the problem only considers uniform costs over items, but non-uniform costs on items are more general. Taking this cue, we study the problem of budgeted sequence submodular maximization (BSSM), which introduces non-uniform costs of items into the sequence selection. This problem can be found in a number of applications such as movie recommendation, course sequence design and so on. Non-uniform costs on items significantly increase the solution complexity and we prove that BSSM is NP-hard. To solve the problem, we first propose a greedy algorithm GBM with an error bound. We also design an anytime algorithm POBM based on Pareto optimization to improve the quality of solutions. Moreover, we prove that POBM can obtain approximate solutions in expected polynomial running time, and converges faster than a state-of-the-art algorithm POSEQSEL for sequence submodular maximization with cardinality constraints. We further introduce optimizations to speed up POBM. Experimental results on both synthetic and real-world datasets demonstrate the performance of our new algorithms.

Actions (login required)

View Item

Downloads