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

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

2006-03-02

arxiv.org/abs/cs/0603010v1

Computer Science

Robotics

Scientific paper

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}$.

Affiliated with

Also associated with

No associations

Rating

Asymptotic constant-factor approximation algorithm for the Traveling Salesperson Problem for Dubins' vehicle does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Asymptotic constant-factor approximation algorithm for the Traveling Salesperson Problem for Dubins' vehicle, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Asymptotic constant-factor approximation algorithm for the Traveling Salesperson Problem for Dubins' vehicle will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-369132