Faster algorithms for orienteering and \(k\)-TSP

DOI10.1016/j.tcs.2022.02.013zbMath1487.68244arXiv2002.07727MaRDI QIDQ2124233

Robert Krauthgamer, Havana Rika, Lee-Ad J. Gottlieb

Publication date: 19 April 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

orienteering; plane sweep algorithm; \(k\)-TSP

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68W25: Approximation algorithms

Uses Software

• VRP

Cites Work

• Unnamed Item
• Orienteering problem: a survey of recent variants, solution approaches and applications
• The Euclidean traveling salesman problem is NP-complete
• Compact, provably-good LPs for orienteering and regret-bounded vehicle routing
• The Vehicle Routing Problem
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Improved algorithms for orienteering and related problems
• Approximation algorithms for deadline-TSP and vehicle routing with time-windows
• The Euclidean Orienteering Problem Revisited
• The orienteering problem
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree
• The prize collecting traveling salesman problem: II. Polyhedral results
• Running Errands in Time: Approximation Algorithms for Stochastic Orienteering
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Approximation Algorithms for Orienteering and Discounted-Reward TSP