Armbruster, SusanneSusanneArmbrusterMnich, MatthiasMatthiasMnichNägele, MartinMartinNägele2024-09-172024-09-172024-08-28International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2024)978-3-9597-7348-5https://hdl.handle.net/11420/49078We present a new (3/2+1/e)-approximation algorithm for the Ordered Traveling Salesperson Problem (Ordered TSP). Ordered TSP is a variant of the classic metric Traveling Salesperson Problem (TSP) where a specified subset of vertices needs to appear on the output Hamiltonian cycle in a given order, and the task is to compute a cheapest such cycle. Our approximation guarantee of approximately 1.868 holds with respect to the value of a natural new linear programming (LP) relaxation for Ordered TSP. Our result significantly improves upon the previously best known guarantee of 5/2 for this problem and thereby considerably reduces the gap between approximability of Ordered TSP and metric TSP. Our algorithm is based on a decomposition of the LP solution into weighted trees that serve as building blocks in our tour construction.enhttps://creativecommons.org/licenses/by/4.0/Travelling Salesperson ProblemPrecedence constraintsLinear programmingApproximation algorithmsNatural Sciences and Mathematics::519: Applied Mathematics, ProbabilitiesNatural Sciences and Mathematics::518: Numerical AnalysisContribution to Conference10.15480/882.1329410.4230/LIPIcs.APPROX/RANDOM.2024.110.15480/882.13294Contribution to Conference