University of Isfahan Transactions on Combinatorics 2251-8657 15 4 2025 12 04 Colored points traveling salesman problem 305 315 30105 10.22108/toc.2025.140814.2153 EN Saeed Asaeedi Department of Computer Science, Faculty of Mathematical Sciences, University of Kashan, P.O.Box 87317-53153, Kashan, I. R. Iran Journal Article 2024 02 24 The Colored Points Traveling Salesman Problem (Colored Points TSP) is introduced in this work as a novel variation of the traditional Euclidean Traveling Salesman Problem (TSP) in which the set of points is partitioned into multiple classes, each of which is represented by a distinct color (or label). The goal is to find a minimum cost cycle that visits all the colors so that each color appears only once. This problem finds diverse applications across various fields, including transportation, goods distribution, postal services, inspection, insurance, and banking. By reducing the traditional TSP to it, we can demonstrate that Colored Points TSP is NP-hard. Here, we offer a $\frac{2\pi r}{3}$-approximation algorithm for this problem when the points are placed on a unit grid, where $r$ denotes the radius of the points' smallest color-spanning circle. The algorithm has been implemented, executed on random datasets, and compared against the brute force method. https://toc.ui.ac.ir/article_30105_70cf2527e15f3dc5695d7b0d796568a1.pdf