English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We consider the rooted prize-collecting walks (PCW) problem, wherein we seeka collection $C$ of rooted walks having minimum prize-collecting cost, which isthe (total cost of walks in $C$) + (total node-reward of nodes not visited byany walk in $C$). This problem arises naturally as the Lagrangian relaxation ofboth orienteering, where we seek a length-bounded walk of maximum reward, andthe $\ell$-stroll problem, where we seek a minimum-length walk covering atleast $\ell$ nodes. Our main contribution is to devise a simple, combinatorialalgorithm for the PCW problem in directed graphs that returns a rooted treewhose prize-collecting cost is at most the optimum value of theprize-collecting walks problem.  We utilize our algorithm to develop combinatorial approximation algorithmsfor two fundamental vehicle-routing problems (VRPs): (1) orienteering; and (2)$k$-minimum-latency problem ($k$-MLP), wherein we seek to cover all nodes using$k$ paths starting at a prescribed root node, so as to minimize the sum of thenode visiting times. Our combinatorial algorithm allows us to sidestep the partwhere we solve a preflow-based LP in the LP-rounding algorithms of Friggstandand Swamy (2017) for orienteering, and in the state-of-the-art$7.183$-approximation algorithm for $k$-MP in Post and Swamy (2015).Consequently, we obtain combinatorial implementations of these algorithms withsubstantially improved running times compared with the current-bestapproximation factors.  We report computational results for our resulting (combinatorialimplementations of) orienteering algorithms, which show that the algorithmsperform quite well in practice, both in terms of the quality of the solutionthey return, as also the upper bound they yield on the orienteering optimum(which is obtained by leveraging the workings of our PCW algorithm).

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