Polynomial-time $(k+\hat{I}\mu )$-approximation for $k$-coloured Non-crossing Euclidean TSP

Daniel Bauer, Jan-Henrik Haunert

Given a $k$-coloured point set $P\subseteq {\mathbb{R}}^2$, the $k$-coloured Non-crossing Euclidean Travelling Salesperson Problem (short $k$-ETSP) asks for $k$ non-crossing closed c…