The Power of Recourse for Online MST and TSP
From MaRDI portal
Publication:5890825
DOI10.1137/130917703zbMath1344.68289OpenAlexW2469267808MaRDI QIDQ5890825
Martin Skutella, José Verschae, Andreas Wiese, Nicole Megow
Publication date: 4 July 2016
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/e2356325d0cdfed4b2e53dcc529d440519bf7a42
Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Online algorithms; streaming algorithms (68W27)
Related Items (17)
Multistage knapsack ⋮ Online maximum matching with recourse ⋮ Online load balancing with general reassignment cost ⋮ The power of amortized recourse for online graph problems ⋮ Online knapsack with removal and recourse ⋮ Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem ⋮ Unnamed Item ⋮ Online Maximum Matching with Recourse ⋮ Symmetry exploitation for online machine covering with bounded migration ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Online Minimum Spanning Tree with Advice ⋮ Online multistage subset maximization problems ⋮ Relaxing the irrevocability requirement for online graph algorithms ⋮ Unnamed Item ⋮ LP-based algorithms for multistage minimization problems
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On-line Steiner trees in the Euclidean plane
- Not all insertion methods yield constant approximate tours in the Euclidean plane
- Constructing competitive tours from local information
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Online graph exploration: New results on old and new algorithms
- Worst-case analysis of a new heuristic for the travelling salesman problem
- A survey of combinatorial optimization problems in multicast routing
- Dynamic Steiner Tree Problem
- Introduction to Stochastic Programming
- Online Steiner Tree with Deletions
- Competitive Maintenance of Minimum Spanning Trees in Dynamic Graphs
- The power of deferral
- The Power of Recourse for Online MST and TSP
- Algorithms for the on-line travelling salesman
This page was built for publication: The Power of Recourse for Online MST and TSP