Prize-collecting TSP with a budget constraint
From MaRDI portal
Publication:5111751
DOI10.4230/LIPICS.ESA.2017.62zbMATH Open1442.90170OpenAlexW2752174437MaRDI QIDQ5111751FDOQ5111751
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
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
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Cites Work
- TSPLIB—A Traveling Salesman Problem Library
- A General Approximation Technique for Constrained Forest Problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- A 2.5-factor approximation algorithm for the \(k\)-MST problem
- Algorithms for the on-line quota traveling salesman problem
- Improved approximation algorithms for prize-collecting Steiner tree and TSP
- Approximation algorithms for distance constrained vehicle routing problems
- Saving an epsilon: a 2-approximation for the \(k\)-MST problem in graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Sharing the cost of multicast transmissions
- Improved algorithms for orienteering and related problems
- A better approximation algorithm for the budget prize collecting tree problem.
- Single-sink network design with vertex connectivity requirements
- Data-driven rebalancing methods for bike-share systems
- Approximation algorithms for the traveling repairman and speeding deliveryman problems
Cited In (8)
- Serving rides of equal importance for time-limited dial-a-ride
- A better approximation algorithm for the budget prize collecting tree problem.
- Data-driven rebalancing methods for bike-share systems
- Exact algorithms for budgeted prize-collecting covering subgraph problems
- Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems
- Title not available (Why is that?)
- Maximizing the number of rides served for time-limited Dial-a-Ride*
- Erratum to “Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems”
Uses Software
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)
