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

Running Errands in Time: Approximation Algorithms for Stochastic Orienteering, 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, Spider covers and their applications, Approximation algorithms for the directed \(k\)-Tour and \(k\)-Stroll problems, Adversarial patrolling with spatially uncertain alarm signals, 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