2026-07-18T08:28:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20994 2024-09-16T06:02:37Z ddc:004 open_access

A (3/2 + 1/e)-Approximation Algorithm for Ordered TSP Armbruster, Susanne Mnich, Matthias Nägele, Martin Travelling Salesperson Problem precedence constraints linear programming approximation algorithms We 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Susanne Armbruster and Matthias Mnich and Martin Nägele 2024 Is Part Of LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2024.1 urn:nbn:de:0030-drops-209943 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.1 eng https://creativecommons.org/licenses/by/4.0/legalcode