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

Abstract-- This article proposes the first known algorithm that achieves a constant-factor approximation of the minim um 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. The Traveling Salesperson Problem (TSP) with its variations is one of the most widely known combinatorial optimization problems. While extensively studied in the literature, these problems continue to attract great inter est from a wide range of fields, including Operations Research, Mathematics and Computer Science. It is quite natural to formulate this problem in context of Dubins' vehicle, i.e., a non-holonomic vehicl e that is constrained to move along paths of bounded curvature, without reversing direction.