Research map / Learning theory and algorithms / Submodular and game algorithms
Submodular Order Functions and Assortment Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace greedy with threshold-based augmentation in submodular order (constant threshold near OPT/2k) | cardinality-constrained submodular order functions · theory (cardinality) | approximation guarantee | Helped |
| Use local search with swap criterion along submodular order instead of threshold add | matroid-constrained submodular order functions · theory (matroid) | approximation guarantee | Helped |
| Noisy value oracle with multiplicative error δ | submodular order algorithms · theory | approximation guarantee: reduced by factor (1-O(nδ/(1-δ))) | Hurt |
| Descending price order as submodular order for MNL assortment revenue | MNL with customization (MMNL) · assortment optimization | approximation guarantee: from Ω(1)/log m (cardinality) and 1/m (budget/matroid) to constant factors | Helped |
Closest papers by meaning
- Consistent Submodular Maximization (ICML 2024 · similarity 0.89)
- Probabilistic Submodular Maximization in Sub-Linear Time (ICML 2017 · similarity 0.89)
- Optimization for Approximate Submodularity (NeurIPS 2018 · similarity 0.89)
- Submodular Maximization beyond Non-negativity: Guarantees, Fast Algorithms, and Applications (ICML 2019 · similarity 0.88)
- Robust Submodular Maximization: A Non-Uniform Partitioning Approach (ICML 2017 · similarity 0.88)
- An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale (ICML 2025 · similarity 0.88)
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.