Approximation algorithms for deadline-TSP and vehicle routing with time-windows

DOI10.1145/1007352.1007385zbMath1192.90216MaRDI QIDQ3580966

Adam Meyerson, Nikhil Bansal, Shuchi Chawla, Avrim L. Blum

Publication date: 15 August 2010

Published in: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1007352.1007385

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90B06: Transportation, logistics and supply chain management

68W25: Approximation algorithms

Related Items

The Robot Routing Problem for Collecting Aggregate Stochastic Rewards, Running Errands in Time: Approximation Algorithms for Stochastic Orienteering, Unnamed Item, Deadline TSP, New approximation algorithms for the rooted budgeted cycle cover problem, New approximation algorithms for the rooted budgeted cycle cover problem, The orienteering problem with time windows applied to robotic melon harvesting, The school bus problem on trees, The capacitated orienteering problem, The directed orienteering problem, Set covering in fuel-considered vehicle routing problems, On the adaptivity gap of stochastic orienteering, Discounted reward TSP, Tour recommendation for groups, Spider covers and their applications, The online food delivery problem on stars, Approximation algorithms for some extensions of the maximum profit routing problem, Faster algorithms for orienteering and \(k\)-TSP, Combinatorial algorithms for rooted prize-collecting walks and applications to orienteering and minimum-latency problems, Delivery route optimization with automated vehicle in smart urban environment, An approximation algorithm for vehicle routing with compatibility constraints, Approximation algorithms for the directed \(k\)-Tour and \(k\)-Stroll problems, Adversarial patrolling with spatially uncertain alarm signals, Orienteering for electioneering, Pruning 2-connected graphs, Approximation algorithms for the traveling repairman and speeding deliveryman problems, Complexity and approximation for traveling salesman problems with profits, Grasp and delivery for moving objects on broken lines, Approximating a vehicle scheduling problem with time windows and handling times, Dynamic Traveling Repair Problem with an Arbitrary Time Window