Research map / Bandits and online learning / Online convex optimization and games
Learning-Augmented Algorithms for Online 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 |
|---|---|---|---|
| Use predicted terminals and bounded subpaths instead of unrestricted predicted-MST paths | IOAPT · Undirected online Steiner tree | competitive ratio: O(η) -> O(log η) | Helped |
| Use predicted terminals with a doubling threshold and offline directed Steiner trees | Directed online Steiner tree · Directed online Steiner tree | competitive ratio: Ω(k) -> O(log k + η) | Helped |
| Use predictions that are about 30% correct | OAPT and IOAPT · Random graphs and road graphs | ratio to online greedy: 30% | Helped |
| Learn predictions on sparse distributions where there is little useful structure to learn | OAPT and IOAPT · Sparse distributions | ratio to online greedy: 1.01 | No clear effect |
| Use predictions learned from a small number of training instances | OAPT and IOAPT · Two-class random graphs and clustered road graphs | ratio to online greedy | Helped |
Closest papers by meaning
- Learning from a Sample in Online Algorithms (NeurIPS 2022 · similarity 0.90)
- A Universal Error Measure for Input Predictions Applied to Online Graph Problems (NeurIPS 2022 · similarity 0.90)
- Approximation algorithms for combinatorial optimization with predictions (ICLR 2025 · similarity 0.88)
- Learning-Augmented Online Covering Problems (ICML 2026 · similarity 0.87)
- On the Universal Near Optimality of Hedge in Combinatorial Settings (NeurIPS 2025 · similarity 0.85)
- Improved Approximations for Hard Graph Problems using Predictions (ICML 2025 · similarity 0.84)
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.