Budgeted Sequence Submodular Maximization

Xuefeng Chen, Liang Feng*, Xin Cao, Yifeng Zeng, Yaqing Hou

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationProceedings of the Thirty-First International Joint Conference on Artificial Intelligence
EditorsLuc De Raedt
Place of PublicationDarmstadt, Germany
PublisherInternational Joint Conferences on Artificial Intelligence
Pages4733-4739
Number of pages7
ISBN (Electronic)9781956792003
DOIs
Publication statusPublished - 16 Jul 2022
EventIJCAI-ECAI 2022, the 31st International Joint Conference on Artificial Intelligence and the 25th European Conference on Artificial Intelligence - Messe Wien, Vienna, Austria
Duration: 23 Jul 202229 Jul 2022
https://ijcai-22.org/

Publication series

NameProceedings of the International Joint Conference on Artificial Intelligence
PublisherInternational Joint Conferences on Artificial Intelligence Organization

Conference

ConferenceIJCAI-ECAI 2022, the 31st International Joint Conference on Artificial Intelligence and the 25th European Conference on Artificial Intelligence
Abbreviated titleIJCAI/ECAI 22
Country/TerritoryAustria
CityVienna
Period23/07/2229/07/22
Internet address

Fingerprint

Dive into the research topics of 'Budgeted Sequence Submodular Maximization'. Together they form a unique fingerprint.

Cite this