Approximation algorithms for the traveling repairman and speeding deliveryman problems

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

zbMATH Keywords

traveling salesman problem; graph algorithms; time windows; approximation algorithms; repairman problem

Mathematics Subject Classification ID

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

• TSPTW

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