Approximation algorithms for the traveling repairman and speeding deliveryman problems
From MaRDI portal
Publication:2428683
DOI10.1007/s00453-011-9515-4zbMath1277.68297MaRDI QIDQ2428683
Barry Wittman, Greg N. Frederickson
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
Related Items
Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems, Prize-Collecting TSP with a Budget Constraint, Deadline TSP, Solving the traveling delivery person problem with limited computational time
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