For the solution of the Euclidean traveling salesman problem with discrete and continuous neighborhoods, three approximation algorithms are introduced. Firstly an $O(a^3)$-approximation algorithm for the case of disjoint and non-fat regions existence is presented. An $O(a^3)$-approximation algorithm for the intersection of non-fat regions with comparable diameters is then analyzed and finally a simple $O(\log n)$-approximation algorithm for continuous non-fat neighborhoods is proposed. The simplicity and the low running-time complexity are the basic characteristics of the presented approximation algorithms.
Reviewer: Vasilis Dimitriou (Chania)