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

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

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

• A 2.5-factor approximation algorithm for the k-MST problem
• A better approximation algorithm for the budget prize collecting tree problem.
• A General Approximation Technique for Constrained Forest Problems
• 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
• 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?)
• 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

(9)

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

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)