A $(5/3+\epsilon)$-Approximation for Tricolored Non-crossing Euclidean TSP
<|reference_start|>A $(5/3+\epsilon)$-Approximation for Tricolored Non-crossing Euclidean TSP: In the Tricolored Euclidean Traveling Salesperson problem, we are given~$k=3$ sets of points in the plane and are looking for disjoint tours, each covering one of the sets. Arora (1998) famously gave a PTAS based on ``patching'' for the case $k=1$ and, recently, Dross et al.~(2023) generalized this result to~$k=2$. Our contribution is a $(5/3+\epsilon)$-approximation algorithm for~$k=3$ that further generalizes Arora's approach. It is believed that patching is generally no longer possible for more than two tours. We circumvent this issue by either applying a conditional patching scheme for three tours or using an alternative approach based on a weighted solution for $k=2$.<|reference_end|>
@article{baligács2024a,
    title={A $(5/3+{\epsilon})$-Approximation for Tricolored Non-crossing Euclidean
  TSP},
    author={J'ulia Balig'acs, Yann Disser, Andreas Emil Feldmann, Anna
  Zych-Pawlewicz},
    journal={arXiv preprint arXiv:2402.13938},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.13938},
    primaryClass={cs.DS}
}