Prize-collecting TSP with a budget constraint

DOI10.4230/LIPICS.ESA.2017.62MaRDI QIDQ5111751zbMATH OpenOpenAlexFDO

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

Publication date 27 May 2020

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

zbMATH Keywords

approximation algorithmstraveling salesman problem

Mathematics Subject Classification ID

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

Recommendations

• Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems
• A better approximation algorithm for the budget prize collecting tree problem.
• scientific article; zbMATH DE number 1445375
• Improved approximation algorithms for (budgeted) node-weighted Steiner problems
• Improved approximation algorithms for prize-collecting Steiner tree and TSP

Cites work

• scientific article; zbMATH DE number 5506214 (Why is no real title available?)
• scientific article; zbMATH DE number 1256763 (Why is no real title available?)
• scientific article; zbMATH DE number 1445375 (Why is no real title available?)
• scientific article; zbMATH DE number 7053373 (Why is no real title available?)
• A 2.5-factor approximation algorithm for the \(k\)-MST problem
• A General Approximation Technique for Constrained Forest Problems
• A better approximation algorithm for the budget prize collecting tree problem.
• Algorithms for the on-line quota traveling salesman problem
• Approximation algorithms for distance constrained vehicle routing problems
• Approximation algorithms for the traveling repairman and speeding deliveryman problems
• Data-driven rebalancing methods for bike-share systems
• Improved algorithms for orienteering and related problems
• Improved approximation algorithms for prize-collecting Steiner tree and TSP
• Saving an epsilon: a 2-approximation for the \(k\)-MST problem in graphs
• Sharing the cost of multicast transmissions
• Single-sink network design with vertex connectivity requirements
• TSPLIB—A Traveling Salesman Problem Library

Cited in

(8)

• Serving rides of equal importance for time-limited dial-a-ride
• Data-driven rebalancing methods for bike-share systems
• Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems
• A better approximation algorithm for the budget prize collecting tree problem.
• scientific article; zbMATH DE number 5886655 (Why is no real title available?)
• Exact algorithms for budgeted prize-collecting covering subgraph problems
• Erratum to “Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems”
• Maximizing the number of rides served for time-limited Dial-a-Ride*

Describes a project that uses

Uses Software

• TSPLIB

This page was built for publication: Prize-collecting TSP with a budget constraint

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111751)