Combinatorial Algorithms for Rooted Prize-Collecting Walks and Applications to Orienteering and Minimum-Latency Problems

Sina Dezfuli, Zachary Friggstad, Ian Post +1

We consider the rooted prize-collecting walks (PCW) problem, wherein we seek a collection $C$ of rooted walks having minimum prize-collecting cost, which is the (total cost of walk…