Research map / Learning theory and algorithms / Submodular and game algorithms
Non-monotone Sequential Submodular Maximization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies sequential submodular maximization with non-monotone submodular functions, proposing sampling-greedy algorithms for flexible and fixed length sequences (0.134 approximation) and improved constant-factor methods for identical utilities, validated on MovieLens video recommendation.
Problem
Selecting and ranking a sequence of items to maximize a weighted sum of prefix-based submodular functions when the functions are non-monotone (adding items can reduce utility), under flexible-length (<=k) and fixed-length (=k) constraints.
Approach
Extends the random-sampling greedy technique for non-monotone submodular maximization to sequences: each considered item is kept with probability p, greedy selects by weighted marginal utility over remaining prefix functions; fixed-length is handled by backup items, and homogeneous utilities allow a complement-function trick for constant factors.
Key results
- Flexible length: SG achieves expected utility over 1.04x10^6 under uniform user distribution versus 7.29x10^5 and 6.75x10^5 for baselines, a 43% increase (k=500).
- Theoretical guarantee: sampling-greedy achieves 0.134-approximation (p=(sqrt3-1)/2) for flexible length, and (1-k/n)*0.134 for fixed length; 0.134/4 for general fixed length with the two-case analysis.
- Shows impossibility of a 0.491-approximation for both flexible and fixed length settings.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use SG instead of COVDIV or QUALITY | MovieLens video recommendation, flexible length · Uniform user type distribution | expected utility: 7.29×10^5 and 6.75×10^5; over 1.04×10^6; a 43% increase | Helped |
| use SG instead of COVDIV or QUALITY | MovieLens video recommendation, flexible length · All tested user type distributions | expected utility | Helped |
| use SG instead of COVDIV or QUALITY | MovieLens video recommendation, fixed length · All tested user type distributions | expected utility | Helped |
| increase the mean μ of the approximated normal user type distribution | MovieLens video recommendation, flexible length · Approximated normal user type distribution | expected utility | Mixed |
| increase the mean μ beyond 400 | SG, MovieLens video recommendation, fixed length · Approximated normal user type distribution | expected utility: 400 | Hurt |
| increase the mean μ beyond 250 | COVDIV, MovieLens video recommendation, fixed length · Approximated normal user type distribution | expected utility: 250 | Hurt |
Surprising findings
- Under fixed length, SG's utility is lower than under flexible length for uniform distribution, while COVDIV's is higher, because forced backup items can have negative marginal contribution.
Limitations
- Fixed-length guarantee degrades with k/n, becoming weak when k is close to n.
- Constant-factor guarantee for general fixed-length case is only 0.134/4 and relies on homogeneous functions for the better bound.
- Experiments limited to one MovieLens-based video recommendation setting with synthetic user-type distributions.
Experimental setup
Datasets: MovieLens
Benchmarks: MovieLens
Metrics: expected utility
Baselines: COVDIV QUALITY
Builds on: sequential submodular maximization random greedy for non-monotone submodular maximization maximal marginal relevance
Closest papers by meaning
- Selecting Sequences of Items via Submodular Maximization (AAAI 2017 · similarity 0.91)
- Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint (NeurIPS 2024 · similarity 0.89)
- Deletion-Robust Submodular Maximization with Knapsack Constraints (AAAI 2024 · similarity 0.88)
- Online and Streaming Algorithms for Constrained k-Submodular Maximization (AAAI 2025 · similarity 0.88)
- Consistent Submodular Maximization (ICML 2024 · similarity 0.87)
- Online Two-Stage Submodular Maximization (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.