Faster algorithms for orienteering and k-TSP

DOI10.1016/J.TCS.2022.02.013zbMATH Open1487.68244arXiv2002.07727OpenAlexW4213005497MaRDI QIDQ2124233FDOQ2124233

Lee-Ad Gottlieb, Robert Krauthgamer, Havana Rika

Publication date: 19 April 2022

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

Abstract: We consider the rooted orienteering problem in Euclidean space: Given $n$ points $P$ in $mathbb{R}^d$, a root point $sinP$ and a budget $mathcalB>0$, find a path that starts from $s$, has total length at most $mathcalB$, and visits as many points of $P$ as possible. This problem is known to be NP-hard, hence we study $(1-delta)$-approximation algorithms. The previous Polynomial-Time Approximation Scheme (PTAS) for this problem, due to Chen and Har-Peled (2008), runs in time $n^{O(dsqrtd/delta)}(logn{)}^{(d/delta{)}^{O(d)}}$, and improving on this time bound was left as an open problem. Our main contribution is a PTAS with a significantly improved time complexity of $n^{O(1/delta)}(logn{)}^{(d/delta{)}^{O(d)}}$. A known technique for approximating the orienteering problem is to reduce it to solving $1/delta$ correlated instances of rooted $k$-TSP (a $k$-TSP tour is one that visits at least $k$ points). However, the $k$-TSP tours in this reduction must achieve a certain excess guarantee (namely, their length can surpass the optimum length only in proportion to a parameter of the optimum called excess) that is stronger than the usual $(1+delta)$-approximation. Our main technical contribution is to improve the running time of these $k$-TSP variants, particularly in its dependence on the dimension $d$. Indeed, our running time is polynomial even for a moderately large dimension, roughly up to $d=O(loglogn)$ instead of $d=O(1)$.

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

zbMATH Keywords

orienteeringplane sweep algorithm\(k\)-TSP

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Cites Work

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

Cited In (2)

• Title not available (Why is that?)
• Approximation algorithms for time-dependent orienteering.

Uses Software

• VRP

This page was built for publication: Faster algorithms for orienteering and \(k\)-TSP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2124233)