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

0656.pdf - Published Version

Download (511kB) | Preview
BSSM_IJCAI_Cam.pdf - Accepted Version

Download (400kB) | Preview
Official URL: https://doi.org/10.24963/ijcai.2022/656


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.

Item Type: Book Section
Additional Information: Funding information: This work was supported in part by NSFC Grants (No. 61876025, 61836005, 62176225, and 61906032), the Fundamental Research Funds for the Central Universities under Grant DUT21TD107, and ARC DE190100663.
Subjects: G400 Computer Science
G500 Information Systems
Depositing User: John Coen
Date Deposited: 19 Aug 2022 09:00
Last Modified: 12 Sep 2022 15:45
URI: https://nrl.northumbria.ac.uk/id/eprint/49921

Actions (login required)

View Item View Item


Downloads per month over past year

View more statistics