A 1.5-Approximation for Symmetric Euclidean Open Loop TSP

A 1.5-Approximation for Symmetric Euclidean Open Loop TSP

Travelling Salesman Problem (TSP) is NP-hard and therefore lacks efficient algorithm that provides optimal solution. So far, a benchmark in this area is Christofides’ Algorithm, which provides an upper bound of 3/2 for metric TSP. In this paper, it is shown that a simple nearest neighbor...

Full description

Bibliographic Details
Main Author: Alok Chauhan
Format: Article
Language:English
Published: IEEE 2024-01-01
Series:IEEE Access
Subjects:
Christofides’ algorithm
5-degree minimum spanning tree
3-degree spanning tree
approximation ratio
symmetric euclidean TSP
2-RNN
Online Access:https://ieeexplore.ieee.org/document/10702593/

Internet

https://ieeexplore.ieee.org/document/10702593/

Similar Items