Prize-Collecting TSP with a Budget Constraint

DOI10.4230/LIPIcs.ESA.2017.62zbMath1442.90170OpenAlexW2752174437MaRDI QIDQ5111751

David P. Williamson, Alice Paul, Daniel Freund, David B. Shmoys, Aaron Ferber

Publication date: 27 May 2020

Full work available at URL: https://doi.org/10.4230/LIPIcs.ESA.2017.62

zbMATH Keywords

traveling salesman problemapproximation algorithms

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items

Data-Driven Rebalancing Methods for Bike-Share Systems ⋮ Serving rides of equal importance for time-limited dial-a-ride

Uses Software

• TSPLIB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A 2.5-factor approximation algorithm for the \(k\)-MST problem
• A better approximation algorithm for the budget prize collecting tree problem.
• Algorithms for the on-line quota traveling salesman problem
• Approximation algorithms for the traveling repairman and speeding deliveryman problems
• Approximation algorithms for distance constrained vehicle routing problems
• Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP
• Improved algorithms for orienteering and related problems
• Saving an epsilon
• TSPLIB—A Traveling Salesman Problem Library
• A General Approximation Technique for Constrained Forest Problems
• Data-Driven Rebalancing Methods for Bike-Share Systems
• Sharing the cost of multicast transmissions