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

Simple item page
dc.creatorSavla, Ketan
dc.creatorFrazzoli, Emilio
dc.creatorBullo, Francesco
dc.date2006-03-02
dc.date.accessioned2026-07-07T07:05:46Z
dc.date.available2026-07-07T07:05:46Z
dc.descriptionThis 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}$.
dc.identifierhttps://arxiv.org/abs/cs/0603010
dc.identifierhttp://arxiv.org/abs/cs/0603010
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/109784
dc.subjectRobotics
dc.titleAsymptotic constant-factor approximation algorithm for the Traveling Salesperson Problem for Dubins' vehicle
dc.typetext

Files

Collections

arXiv