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

DOI10.1145/1007352.1007385zbMath1192.90216OpenAlexW2158591664MaRDI 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

Programming involving graphs or networks (90C35) Transportation, logistics and supply chain management (90B06) Approximation algorithms (68W25)

Related Items (30)

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

This page was built for publication: Approximation algorithms for deadline-TSP and vehicle routing with time-windows