The Power of Recourse for Online MST and TSP

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

zbMATH Keywords

traveling salesmanonline algorithmsminimum spanning treerecourse

Mathematics Subject Classification ID

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

• Concorde

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