Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems

DOI10.1287/moor.2019.1002zbMath1456.90137OpenAlexW2994566040WikidataQ101127888 ScholiaQ101127888MaRDI QIDQ5119847

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

Publication date: 1 September 2020

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://hdl.handle.net/1721.1/136017

zbMATH Keywords

constrained optimizationtraveling salesman problemapproximation algorithms

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (9)

Exact algorithms for budgeted prize-collecting covering subgraph problems ⋮ Combinatorial algorithms for rooted prize-collecting walks and applications to orienteering and minimum-latency problems ⋮ Exact and Approximation Algorithms for the Expanding Search Problem ⋮ Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Directed Network Design Problems ⋮ Hybrid genetic algorithm for undirected traveling salesman problems with profits ⋮ A unified approach to approximate partial, prize-collecting, and budgeted sweep cover problems ⋮ Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the asymmetric traveling salesman problem ⋮ A greedy algorithm for finding maximum spanning trees in infinite graphs ⋮ Serving rides of equal importance for time-limited dial-a-ride

Uses Software

• TSPLIB

Cites Work

• 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
• Solving Connected Subgraph Problems in Wildlife Conservation
• Saving an epsilon
• TSPLIB—A Traveling Salesman Problem Library
• A General Approximation Technique for Constrained Forest Problems
• Sharing the cost of multicast transmissions

This page was built for publication: Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems