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:
- Order Matters: The sequence (Transformers 1, Transformers 2) yields different utility than the reverse.
- Costs Vary: Each item has an associated cost (e.g., rental price or time commitment).
- Budgets are Finite: The total cost of the selected sequence must not exceed a specified limit.
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.
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