Budgeted Sequence Submodular Maximization With Uniform and Non-Uniform Costs

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

25 Downloads (Pure)

Abstract

The problem of picking a sequence of items that maximizes a given submodular function over the item sequence exists in many practical applications. Existing studies on this problem only consider uniform costs on items. However, it is more general that items have non-uniform costs. Taking this cue, in this article, we study the problem of b udgeted s equence s ubmodular m aximization (BSSM), which considers both uniform and non-uniform item costs in the sequence selection. This problem widely appears in many applications such as movie recommendation and course learning. For BSSM with uniform costs, we first prove a new approximation ratio for an existing algorithm OMEGA, and then propose an anytime randomized iterative algorithm POBM which converges faster than a state-of-the-art method POSEQSEL in obtaining approximate solutions. We also develop some optimization techniques for improving the efficiency of POBM. For BSSM with non-uniform costs, we design a greedy algorithm GBM with a guaranteed error bound, and prove that POBM can find approximate solutions in a reasonable time. The results of the experimental study on both synthetic and real datasets demonstrate the excellent performance of our algorithms.
Original languageEnglish
Pages (from-to)503-518
Number of pages16
JournalIEEE Transactions on Emerging Topics in Computational Intelligence
Volume8
Issue number1
Early online date29 Aug 2023
DOIs
Publication statusPublished - 1 Feb 2024

Keywords

  • Approximation algorithms
  • Computational intelligence
  • Costs
  • Greedy algorithms
  • Iterative methods
  • Motion pictures
  • Optimization
  • Sequence submodular maximization
  • evolutionary optimization
  • experimental study
  • submodular optimization
  • theoretical analysis

Cite this