AI Paper Atlas

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

AAAI 2018 · Learning theory and algorithms › Submodular and game algorithms · approach: Monotone submodular maximization · 11 citations (OpenAlex)

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 changedWhereMeasuredEffect
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 -> 100Improved
use u_dom instead of approximation-ratio bound u_app as heuristic (ablation)BFSTC · COV artificial alpha=0.7# instances solved: 47 -> 100Improved
use u_dom instead of u_mod (ablation)BFSTC · COV artificial alpha=0.7# nodes pushed: 1.39e+6 -> 1.00e+0Improved
use u_dom instead of u_mod (ablation)BFSTC · COV artificial alpha=1.0# nodes pushed: 2.92e+6 -> 1.55e+6Improved
use u_dom instead of u_mod (ablation)BFSTC · COV artificial alpha=0.9running time (s): 4.80e+2 -> 6.32e+1Improved
use u_dom instead of u_app (ablation)BFSTC · COV artificial alpha=1.0running time (s): 8.04e+2 -> 4.75e+1Improved
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+0Improved
use u_dom instead of u_mod or u_app on real-world instancesBFSTC · real COV/LOC/INFtime and nodesImproved
use u_mod or u_app instead of u_dom on real-world instances (ablation)BFSTC · real COV/LOC/INFobjective valueMixed

Closest papers by meaning

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy