Combinatorial algorithms for rooted prize-collecting walks and applications to orienteering and minimum-latency problems

DOI10.1007/978-3-031-06901-7_15zbMath1497.90168arXiv2111.07414OpenAlexW3212127876MaRDI QIDQ2164695

Ian Post, Chaitanya Swamy, Sina Dezfuli, Zachary Friggstad

Publication date: 16 August 2022

Full work available at URL: https://arxiv.org/abs/2111.07414

zbMATH Keywords

combinatorial approximation algorithmsprize-collecting costrooted walk

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• On solving cycle problems with branch-and-cut: extending shrinking and exact subcycle elimination separation algorithms
• Compact, provably-good LPs for orienteering and regret-bounded vehicle routing
• The Vehicle Routing Problem
• The minimum latency problem
• Approximation algorithms for distance constrained vehicle routing problems
• Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems
• Improved algorithms for orienteering and related problems
• Approximation algorithms for deadline-TSP and vehicle routing with time-windows
• TSPLIB—A Traveling Salesman Problem Library
• Solving the Orienteering Problem through Branch-and-Cut
• Preserving and Increasing Local Edge-Connectivity in Mixed Graphs
• Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems
• Approximation algorithms for regret-bounded vehicle routing and applications to distance-constrained vehicle routing
• Linear Programming-based Approximation Algorithms for Multi-Vehicle Minimum Latency Problems (Extended Abstract)
• Approximation Algorithms for Orienteering and Discounted-Reward TSP

This page was built for publication: Combinatorial algorithms for rooted prize-collecting walks and applications to orienteering and minimum-latency problems