Research map / Learning theory and algorithms / Combinatorial and search optimization
Min-Max Propagation
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 |
|---|---|---|---|
| Use min-value decimation instead of max-support decimation (ablation) | min-max propagation on makespan · Makespan identical machines (Fig. 6) | min-max ratio to lower bound (lower is better) | Mixed |
| Min-max propagation (max-support decimation) vs LPT on identical-machine makespan | min-max propagation · Makespan identical machines (Fig. 6) | min-max ratio to lower bound (lower is better) | Mixed |
| Min-max propagation vs Vinyals et al. 2013 on unrelated-machine makespan | min-max propagation · Makespan unrelated machines (Fig. 7) | min-max ratio to LP relaxation (higher is better) | Mixed |
| Sum-product reduction with PBP vs min-max propagation on random Erdos-Renyi min-max instances | sum-product reduction (PBP CSP solver) · Random min-max graphs N=10,100, D=4,6,8 | min-max solution value (lower is better) | Helped |
| Decimation scheme choice (random, min-value, max-support) (ablation) | min-max propagation on random graphs · Random min-max graphs | min-max solution value | No clear effect |
Closest papers by meaning
- Beyond Trees: Analysis and Convergence of Belief Propagation in Graphs with Multiple Cycles (AAAI 2020 · similarity 0.87)
- The Linearization of Belief Propagation on Pairwise Markov Random Fields (AAAI 2017 · similarity 0.87)
- Separate but Equal: Equality in Belief Propagation for Single Cycle Graphs (AAAI 2023 · similarity 0.87)
- Learning in Deep Factor Graphs with Gaussian Belief Propagation (ICML 2024 · similarity 0.85)
- Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems (NeurIPS 2024 · similarity 0.84)
- Learning-Augmented Streaming Algorithms for Approximating Boolean Max-CSPs (NeurIPS 2026 · similarity 0.83)
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.