Budgeted Sequence Submodular Maximization With Uniform and Non-Uniform Costs

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.