Approximation algorithms for the traveling repairman and speeding deliveryman problems
From MaRDI portal
Publication:2428683
DOI10.1007/s00453-011-9515-4zbMath1277.68297MaRDI QIDQ2428683
Greg N. Frederickson, Barry Wittman
Publication date: 26 April 2012
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-011-9515-4
traveling salesman problem; graph algorithms; time windows; approximation algorithms; repairman problem
90C27: Combinatorial optimization
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Analysis of Christofides' heuristic: some paths are more difficult than cycles
- Embedding relaxations in global constraints for solving TSP and TSPTW
- Better approximation ratios for the single-vehicle scheduling problems on line-shaped networks
- Approximation algorithms for deadline-TSP and vehicle routing with time-windows
- Approximation Algorithms for the Traveling Repairman and Speeding Deliveryman Problems with Unit-Time Windows
- Poly-logarithmic Approximation Algorithms for Directed Vehicle Routing Problems
- Special cases of traveling salesman and repairman problems with time windows
- New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen
- On approximating a geometric prize-collecting traveling salesman problem with time windows
- The Traveling Salesman Problem with Distances One and Two
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Approximation Algorithms for Orienteering and Discounted-Reward TSP