Research map / Learning theory and algorithms / Combinatorial and search optimization
Separator-Based Pruned Dynamic Programming for Steiner Tree
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 |
|---|---|---|---|
| add separator-based pruning to the Dreyfus-Wagner/EMV dynamic program (ablation) | EMV DP · PACE instances | running time | Helped |
| add the binary-tree data structure for subset enumeration (ablation) | Pruned DP · PACE instances | running time | Helped |
| add meet-in-the-middle technique (ablation) | Pruned DP · PACE instances | running time | Helped |
| use pruned DP instead of A* search (HSV) on near-planar Group instances | Steiner tree solver · Group (89 instances) | instances solved: 16 -> 87 | Helped |
| use pruned DP instead of SCIP-JACK on VLSI instances | Steiner tree solver · VLSI (40 instances) | instances solved: 20 -> 32 | Helped |
| use pruned DP instead of SCIP-JACK on Rectilinear instances | Steiner tree solver · Rectilinear (143 instances) | instances solved: 138 -> 113 | Hurt |
| use pruned DP instead of SCIP-JACK on Random graphs | Steiner tree solver · Random (133 instances) | instances solved: 96 -> 91 | Hurt |
| use pruned DP instead of SCIP-JACK on Vienna instances | Steiner tree solver · Vienna (210 instances) | instances solved: 129 -> 42 | Hurt |
Closest papers by meaning
- Steiner Tree Problems with Side Constraints Using Constraint Programming (AAAI 2016 · similarity 0.87)
- Learning-Augmented Algorithms for Online Steiner Tree (AAAI 2022 · similarity 0.85)
- Parallel Beam Search Algorithms for Domain-Independent Dynamic Programming (AAAI 2024 · similarity 0.84)
- NN-Steiner: A Mixed Neural-Algorithmic Approach for the Rectilinear Steiner Minimum Tree Problem (AAAI 2024 · similarity 0.84)
- Approximation algorithms for combinatorial optimization with predictions (ICLR 2025 · similarity 0.83)
- Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching (ICML 2024 · similarity 0.81)
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.