Research map / Bandits and online learning / Online convex optimization and games
Learning-Augmented Algorithms for Online TSP on the Line
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 request locations to guide service order | FARFIRST · Closed online TSP on the line, perfect predictions | competitive ratio: 1.64 -> 1.5 | Helped |
| Use predicted request locations to choose the first side | NEARFIRST · Open online TSP on the line, perfect predictions | competitive ratio: 2 -> 1.66 | Helped |
| Add a prediction of the request on which OPT may finish | Open online TSP on the line with LOCATIONS predictions · Open online TSP on the line, perfect predictions | competitive ratio: 1.66 -> 1.33 | Helped |
| Use predicted request locations to guide service order | FARFIRST · Closed online TSP on the line, arbitrary prediction error | competitive ratio: min{3(1 + η)/2, 3} | Mixed |
| Use predicted request locations to choose the first side | NEARFIRST · Open online TSP on the line, arbitrary prediction error | competitive ratio: min{f(η), 3} | Mixed |
| Add a prediction of OPT's final request to location predictions | PIVOT · Open online TSP on the line, arbitrary prediction errors | competitive ratio: min{f(η, δ), 3} | Mixed |
| Use the LOCATIONS prediction model | Any algorithm for closed online TSP on the line · Closed online TSP on the line, perfect predictions | competitive ratio lower bound: 1.5 | Helped |
| Use the LOCATIONS prediction model | Any algorithm for open online TSP on the line · Open online TSP on the line, perfect predictions | competitive ratio lower bound: 1.44 | Helped |
| Add a prediction of OPT's final request to location predictions | Any algorithm for open online TSP on the line · Open online TSP on the line, perfect LOCATIONS+FINAL predictions | competitive ratio lower bound: 1.25 | Helped |
Closest papers by meaning
- Unify ML4TSP: Drawing Methodological Principles for TSP and Beyond from Streamlined Design Space of Learning and Search (ICLR 2025 · similarity 0.88)
- TSP with Predictions: Heatmap to Tour with Provable Guarantees (ICML 2026 · similarity 0.88)
- Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problems (ICML 2024 · similarity 0.85)
- DualOpt: A Dual Divide-and-Optimize Algorithm for the Large-scale Traveling Salesman Problem (AAAI 2025 · similarity 0.85)
- Learning-Augmented Online Bidding in Stochastic Settings (NeurIPS 2025 · similarity 0.84)
- Learning-Augmented Algorithms for the Bahncard Problem (NeurIPS 2024 · 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.