Research map / Learning theory and algorithms / Clustering
Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion
Nate Veldt, Thomas Stanley, Benjamin W Priest, Trevor Steil, Keita Iwabuchi, T.S. Jayram, Grace J Li, Geoffrey Sanders
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 |
|---|---|---|---|
| add a few extra representatives per component (MultiRepMFC with budget b > 0 vs MFC-Approx b=0) (ablation) | MultiRepMFC · Cooking, GreenGenes, FashionMNIST, Names-US | cost ratio vs MFC-OPT | Improved |
| allocate representatives with dynamic programming instead of greedy or fixed per-component (ablation) | MultiRepMFC · Cooking, GreenGenes, FashionMNIST, Names-US | cost ratio at fixed runtime | Improved |
| use Greedy allocation instead of Fixed(l) allocation (ablation) | MultiRepMFC · four datasets | cost ratio at fixed runtime | Hurt |
| use DP allocation to minimize instance-specific bound alpha (ablation) | MultiRepMFC · four datasets | alpha bound | Improved |
| use multiple representatives with large budget on imbalanced forests | MultiRepMFC · Names-US | runtime vs MFC-OPT | No clear effect |
| tighter analysis of one-arbitrary-representative algorithm | MFC-Approx · worst-case approximation for MFC | approximation factor: 2.62 -> 2 | Improved |
Closest papers by meaning
- Approximate Forest Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees (ICML 2025 · similarity 0.96)
- Learning Ultrametric Trees for Optimal Transport Regression (AAAI 2024 · similarity 0.85)
- Complete-Tree Space Favors Data-Efficient Link Prediction (ICML 2025 · similarity 0.83)
- Distribution Learning Meets Graph Structure Sampling (NeurIPS 2025 · similarity 0.82)
- On the Universal Near Optimality of Hedge in Combinatorial Settings (NeurIPS 2025 · similarity 0.82)
- Approximation algorithms for combinatorial optimization with predictions (ICLR 2025 · similarity 0.82)
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.
