Research map / Learning theory and algorithms / Submodular and game algorithms
Accelerated Best-First Search With Upper-Bound Computation for Submodular Function Maximization
Shinsaku Sakaue, Masakazu Ishihata
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 |
|---|---|---|---|
| use proposed dominant-element upper bound u_dom as heuristic instead of modular-function bound u_mod (ablation) | BFSTC · COV artificial alpha=0.7 | # instances solved: 84 -> 100 | Improved |
| use u_dom instead of approximation-ratio bound u_app as heuristic (ablation) | BFSTC · COV artificial alpha=0.7 | # instances solved: 47 -> 100 | Improved |
| use u_dom instead of u_mod (ablation) | BFSTC · COV artificial alpha=0.7 | # nodes pushed: 1.39e+6 -> 1.00e+0 | Improved |
| use u_dom instead of u_mod (ablation) | BFSTC · COV artificial alpha=1.0 | # nodes pushed: 2.92e+6 -> 1.55e+6 | Improved |
| use u_dom instead of u_mod (ablation) | BFSTC · COV artificial alpha=0.9 | running time (s): 4.80e+2 -> 6.32e+1 | Improved |
| use u_dom instead of u_app (ablation) | BFSTC · COV artificial alpha=1.0 | running time (s): 8.04e+2 -> 4.75e+1 | Improved |
| add proposed termination condition (greedy solution certified alpha-optimal) with u_dom (ablation) | BFSTC · artificial COV/LOC/INF alpha<=0.7 | # nodes pushed: 1.00e+0 | Improved |
| use u_dom instead of u_mod or u_app on real-world instances | BFSTC · real COV/LOC/INF | time and nodes | Improved |
| use u_mod or u_app instead of u_dom on real-world instances (ablation) | BFSTC · real COV/LOC/INF | objective value | Mixed |
Closest papers by meaning
- Submodular Maximization in Clean Linear Time (NeurIPS 2022 · similarity 0.91)
- Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity (ICML 2021 · similarity 0.90)
- Practical Parallel Algorithms for Submodular Maximization Subject to a Knapsack Constraint with Nearly Optimal Adaptivity (AAAI 2023 · similarity 0.90)
- Nearly Linear-Time, Parallelizable Algorithms for Non-Monotone Submodular Maximization (AAAI 2021 · similarity 0.90)
- Online Two-Stage Submodular Maximization (NeurIPS 2025 · 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.
