Research map / Learning theory and algorithms / Combinatorial and search optimization
NN-Steiner: A Mixed Neural-Algorithmic Approach for the Rectilinear Steiner Minimum Tree Problem
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes NN-Steiner, a mixed neural-algorithmic framework that replaces the DP components of Arora's PTAS with four bounded-size MLPs to approximately solve rectilinear Steiner minimum tree problems.
Problem
Computing rectilinear Steiner minimum trees (RSMT) for VLSI design: exact and approximation methods are too slow in practice, and existing neural approaches (REST) struggle to generalize to large pointsets.
Approach
Replace the costly bottom-up dynamic programming and top-down backtracking of Arora's PTAS with four bounded-size MLPs (base case, DP inductive step, root retrieval, backward retrieval), so the learned components are fixed-size and reusable across input sizes, followed by algorithmic refinement.
Key results
- For 500+ point pointsets NN-Steiner beats FLUTE (A=18), e.g. -0.67% at 500, -2.99% at 5000 points, while REST is +22.68% at 500 and +147.48% at 5000.
- At 50 points NN-Steiner is 2.10% longer than FLUTE, and GeoSteiner (exact) is -0.54% at 50 points, so NN-Steiner is not best on small instances.
- Runtime of NN-Steiner scales approximately linearly (1021 s total for 100 pointsets of 5000 points vs 613.77 s for FLUTE).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add cell/subtree refinement steps to NN-Steiner tree construction (vs. none) (ablation) | NN-Steiner · Uniform pointsets, 500-5000 points | avg % length diff vs FLUTE: refinement contributes most; e.g. 500 pts: 3.39 without cell refinement, 0.39 without subtree refinement, -0.67 full | Helped |
| Replace NN-built tree with MST over input points V (refinement kept) (ablation) | NN-Steiner · Uniform pointsets, 5000 points | avg % length diff vs FLUTE: -2.46 vs -2.99 full | Hurt |
| Apply refinement to FLUTE output instead of NN-Steiner tree (ablation) | FLUTE · Uniform pointsets, 5000 points | avg % length diff vs FLUTE: -0.33 vs 0.00 baseline | No clear effect |
| Use portal count m=3 instead of m=15 (ablation) | NN-Steiner · Uniform pointsets, 50-5000 points | avg % length diff vs FLUTE: worse at 50-200 pts (2.36, 2.05, 0.99 vs 2.10, 1.38, 0.74); slightly worse at 5000 (-2.76 vs -2.99); runtime drops | Mixed |
| Use leaf capacity k_b=1 instead of 4 (ablation) | NN-Steiner · Uniform pointsets, 50-5000 points | avg % length diff vs FLUTE: e.g. 50 pts 2.78 vs 2.10; 5000 pts -1.63 vs -2.99 | Hurt |
| Use leaf capacity k_b=7 instead of 4 (ablation) | NN-Steiner · Uniform pointsets, 50-5000 points | avg % length diff vs FLUTE: better at 5000 (-3.18 vs -2.99) but worse at 100-200 (1.64, 0.37 vs 1.38, 0.74) | Mixed |
| Use NN-Steiner instead of FLUTE for large instances | NN-Steiner vs FLUTE · Uniform pointsets, 500+ points | avg % length diff vs FLUTE: -0.67 at 500 to -2.99 at 5000 (FLUTE = 0) | Helped |
| Use NN-Steiner instead of REST (RL) for large instances | NN-Steiner vs REST · Uniform pointsets, 5000 points | avg % length diff vs FLUTE: -2.99 vs 147.48 | Helped |
| Train on uniform pointsets and test on mixture/non-isotropic normal distributions | NN-Steiner · Mixture and non-isotropic normal pointsets, 50-2000 points | avg % length diff vs FLUTE: non-isotropic within ~0.1 of uniform; mixture slightly worse at small sizes (2.54 vs 2.10 at 50) | No clear effect |
Surprising findings
- Refinement steps contribute most of the gain; applying refinement to an MST over input points alone gets close to full NN-Steiner performance at large sizes.
- Refinement applied to FLUTE output yields only small improvement (about -0.33% at 5000 points), suggesting NN tree topology is what helps at scale.
Limitations
- Slower than FLUTE and worse than FLUTE and GeoSteiner on small pointsets (50 points)
- Theoretical bounded-size result depends exponentially on m and r; practical version is heuristic
- Only Manhattan planar case evaluated; 3D and obstacle-avoiding variants left to future work
Experimental setup
Datasets: synthetic uniform pointsets on integer grid (120,000 training pointsets labeled by GeoSteiner)
Benchmarks: uniform random pointsets 50-5000 points mixture-normal and non-isotropic normal pointsets
Metrics: average percent length difference vs FLUTE runtime in seconds
Baselines: FLUTE GeoSteiner REST
Builds on: Arora's PTAS NN-Baker REST
Closest papers by meaning
- NeuralSteiner: Learning Steiner Tree for Overflow-avoiding Global Routing in Chip Design (NeurIPS 2024 · similarity 0.87)
- Geometric Algorithms for Neural Combinatorial Optimization with Constraints (NeurIPS 2025 · similarity 0.85)
- A Circuit Domain Generalization Framework for Efficient Logic Synthesis in Chip Design (ICML 2024 · similarity 0.84)
- UDC: A Unified Neural Divide-and-Conquer Framework for Large-Scale Combinatorial Optimization Problems (NeurIPS 2024 · similarity 0.84)
- Efficient Bisection Projection to Ensure Neural-Network Solution Feasibility for Optimization over General Set (ICML 2025 · similarity 0.84)
- Towards Next-Generation Logic Synthesis: A Scalable Neural Circuit Generation Framework (NeurIPS 2024 · 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.