Routing on Sparse Graphs with Non-metric Costs for the Prize-collecting Travelling Salesperson Problem

Patrick O'Hara, M. S. Ramanujan, Theodoros Damoulas

In many real-world routing problems, decision makers must optimise over sparse graphs such as transportation networks with non-metric costs on the edges that do not obey the triang…