Budgeted Sequence Submodular Maximization

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

Abstract

This paper introduces Budgeted Sequence Submodular Maximization (BSSM), a framework for selecting the best ordered sequence of items under non-uniform cost constraints and a limited budget. We prove the problem is NP-hard and propose two novel algorithms: a greedy approach (GBM) and a Pareto-optimization-based anytime algorithm (POBM). Experimental results on synthetic and real-world datasets (MovieLens, XuetangX) demonstrate that our methods outperform existing state-of-the-art approaches in both solution quality and convergence speed.

Introduction

Submodular optimization is a cornerstone of decision-making under diminishing returns. Traditionally, research has focused on selecting a subset of items where order is irrelevant and costs are uniform. However, real-world applications—such as recommending a sequence of movies or a curriculum of online courses—require considering both the order of items and their varying costs. For instance, watching a movie franchise in chronological order provides higher utility than a random sequence, and different movies have different rental prices. This paper addresses the Budgeted Sequence Submodular Maximization (BSSM) problem, filling a critical gap in sequence selection under non-uniform budget constraints.

Problem Formulation

The BSSM problem involves selecting an ordered sequence of items from a set to maximize a submodular utility function, subject to a total cost budget. Unlike subset selection, the utility here depends on the sequence:

  1. Order Matters: The sequence (Transformers 1, Transformers 2) yields different utility than the reverse.
  2. Costs Vary: Each item has an associated cost (e.g., rental price or time commitment).
  3. Budgets are Finite: The total cost of the selected sequence must not exceed a specified limit.
Example of sequences with varying costs and dependencies.

Proposed Methods

We propose two primary algorithms to solve the BSSM problem:

Greedy Budgeted Maximization (GBM)

Standard greedy algorithms typically select items based on immediate gain. GBM improves upon this by selecting the "edge" (a pair of items in sequence) with the highest marginal cost-effective value. This "bang-for-your-buck" approach prevents the algorithm from exhausting the budget prematurely on high-utility but expensive items.

Pareto Optimization for Budgeted Maximization (POBM)

POBM is an "anytime" algorithm that treats BSSM as a bi-objective optimization problem: maximizing utility while minimizing cost. It maintains a "Pareto front" of the most efficient trade-offs found during execution. POBM introduces a specialized REORDER function to optimize sequences for a given set of items and employs "quick dominance checks" to scale to large datasets.

Experimental Evaluation

The algorithms were evaluated on three types of data:

  • Synthetic Datasets: Directed Acyclic Graphs (DAGs) with varying "out-degrees" to test structural complexity.
  • MovieLens 1M (MOV): Movie sequences with costs derived from Amazon DVD prices.
  • XuetangX (XTX): Online course sequences with costs based on completion time.

Key Results

Our experiments show that GBM and POBM consistently outperform OMEGA, the previous state-of-the-art for sequence selection, which struggles with non-uniform costs.

Approximation ratio comparison for Modular and Submodular utility functions across different out-degrees.

Key findings include:

  • Superior Approximation: POBM and GBM achieve significantly higher approximation ratios than OMEGA, especially as the complexity of item dependencies (out-degree) increases.
  • Efficiency: An optimized version, POBMOpt, reaches high-quality solutions (over 95% approximation ratio) rapidly on real-world datasets.
  • Robustness: The performance gap between our methods and baselines widens as the budget increases, demonstrating superior handling of complex constraints.

Conclusion

BSSM provides a robust framework for sequence selection under realistic budget constraints. While current theoretical guarantees are strongest for Directed Acyclic Graphs (DAGs), the algorithms remain effective for general graphs. Future work will explore parallelizing POBM to handle massive datasets more efficiently.

Summary updated

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.
BibTeX
@inproceedings{chen2022budgeted,
  author = {Xuefeng Chen and Liang Feng and Xin Cao and Yifeng Zeng and Yaqing Hou},
  title = {{Budgeted Sequence Submodular Maximization}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/656},
}
Figure