Research map / Learning theory and algorithms / Submodular and game algorithms
Joint M-Best-Diverse Labelings as a Parametric Submodular Minimization
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 sequential DivMBest with parametric (Joint-DivMBest-equivalent) solver computing M labelings via closed-form gamma values | M-best diverse labelings with Hamming diversity · Interactive segmentation (super-pixel, PASCAL VOC 2010 subset) | runtime (ms): e.g. 11.6 -> 4.3 ms at M=6; 15.4 -> 6.2 ms at M=10 | Helped |
| Replace DivMBest with the exact parametric solver | M-best diverse labelings · Interactive segmentation (super-pixel) | quality (per-pixel accuracy): 93.16 -> 95.13 at M=2; 95.02 -> 96.01 at M=6 | Helped |
| Use parametric solver instead of Joint-DivMBest (exact solver of Kirillov/Batra-style joint energy) | Joint M-best diverse labelings · Interactive segmentation (super-pixel) | runtime (ms): 80.3 -> 8.4 ms at M=10 (sequential); 5.5 -> 2.2 ms at M=2 | Helped |
| Parallel vs sequential parametric solver (ablation) | Parametric M-best solver · Foreground/background segmentation (VOC 2012) | runtime: Parametric-parallel clear winner over Parametric-sequential and DivMBest | Helped |
| Replace DivMBest with parametric solver | M-best diverse labelings · Foreground/background segmentation (VOC 2012, 451 images) | IoU: Parametric curve above DivMBest across M=1..10 | Helped |
| Use parametric solver instead of DivMBest | M-best diverse labelings · Foreground/background segmentation (VOC 2012) | runtime (s): Parametric-sequential faster than DivMBest; difference grows with M | Helped |
| Use Hamming-distance diversity (concave) instead of non-concave measures | Joint-DivMBest parametric reformulation · Theory (Theorem 2, Corollary 1) | nestedness/exact solution | No clear effect |
Closest papers by meaning
- Regularized Submodular Maximization at Scale (ICML 2021 · similarity 0.86)
- GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility (NeurIPS 2025 · similarity 0.86)
- Memory Efficient Max Flow for Multi-Label Submodular MRFs (CVPR 2016 · similarity 0.86)
- Weakly Submodular Maximization Beyond Cardinality Constraints: Does Randomization Help Greedy? (ICML 2018 · similarity 0.86)
- Corporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems (NeurIPS 2025 · similarity 0.85)
- Online Two-Stage Submodular Maximization (NeurIPS 2025 · similarity 0.84)
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.