2026-07-26T04:14:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21086 2024-09-23T09:13:16Z ddc:004 open_access

A (5/3+ε)-Approximation for Tricolored Non-Crossing Euclidean TSP Baligács, Júlia Disser, Yann Feldmann, Andreas Emil Zych-Pawlewicz, Anna Approximation Algorithms geometric Network Optimization Euclidean TSP non-crossing Structures 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+ε)-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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Júlia Baligács and Yann Disser and Andreas Emil Feldmann and Anna Zych-Pawlewicz 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.15 urn:nbn:de:0030-drops-210862 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.15 eng https://creativecommons.org/licenses/by/4.0/legalcode