Algorithms for the universal and a priori TSP
From MaRDI portal
Publication:924875
DOI10.1016/j.orl.2007.04.009zbMath1151.90040OpenAlexW2068317683MaRDI QIDQ924875
Frans Schalekamp, David B. Shmoys
Publication date: 29 May 2008
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.orl.2007.04.009
Related Items (10)
Routing Under Uncertainty: The a priori Traveling Repairman Problem ⋮ Approximation algorithms for the a priori traveling repairman ⋮ On the Complexity of Master Problems ⋮ Universal Algorithms for Clustering Problems ⋮ Spaces that can be ordered effectively: virtually free groups and hyperbolicity ⋮ A priori TSP in the Scenario Model ⋮ The A priori traveling repairman problem ⋮ A priori TSP in the scenario model ⋮ Designing Networks with Good Equilibria under Uncertainty ⋮ A constant approximation algorithm for the uniform a priori capacitated vehicle routing problem with unit demands
Cites Work
- An O(N log N) planar travelling salesman heuristic based on spacefilling curves
- Worst-case examples for the spacefilling curve heuristic for the Euclidean traveling salesman problem
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Spacefilling curves and the planar travelling salesman problem
- Universal approximations for TSP, Steiner tree, and set cover
- Improved lower and upper bounds for universal TSP in planar metrics
- Oblivious network design
- A Priori Solution of a Traveling Salesman Problem in Which a Random Subset of the Customers Are Visited
- Sometimes Travelling is Easy: The Master Tour Problem
- The structure of circular decomposable metrics
- A Priori Optimization
- A tight bound on approximating arbitrary metrics by tree metrics
- A tight bound on approximating arbitrary metrics by tree metrics
This page was built for publication: Algorithms for the universal and a priori TSP
