Asymptotic constant-factor approximation algorithm for the Traveling Salesperson Problem for Dubins' vehicle

2006/03/02 by Ketan Savla, Savla, Ketan, Emilio Frazzoli +3
Computer Science · Engineering · #Data Management and Algorithms #FOS: Computer and information sciences #Robotic Path Planning Algorithms #Robotics (cs.RO) #Vehicle Routing Optimization Methods #cs.RO

paper · pdf · doi:10.48550/arxiv.cs/0603010

arxiv created 2006/03/02 · openalex publication_date 2006/03/02 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This article proposes the first known algorithm that achieves a constant-factor approximation of the minimum length tour for a Dubins' vehicle through n points on the plane. By Dubins' vehicle, we mean a vehicle constrained to move at constant speed along paths with bounded curvature without reversing direction. For this version of the classic Traveling Salesperson Problem, our algorithm closes the gap between previously established lower and upper bounds; the achievable performance is of order n^2/3.

Citations

• On Curves of Minimal Length with a Constraint on Average Curvature, and with Prescribed Initial and Terminal Positions and Tangents

Related

• A Gradient Descent Method for The Dubins Traveling Salesman Problem
• On Tightly Bounding the Dubins Traveling Salesman's Optimum
• Improved FPT Approximation for Non-metric TSP
• Approximation Algorithms for the Traveling Repairman and Speeding Deliveryman Problems
• On Efficient Computation of Shortest Dubins Paths Through Three Consecutive Points