A (3/2 + 1/e)-Approximation Algorithm for Ordered TSP
OPEN ACCESS
Loading...
Author / Producer
Date
2024-09
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
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.
Permanent link
Publication status
published
Book title
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Volume
317
Pages / Article No.
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Event
27th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2024)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Travelling Salesperson Problem; precedence constraints; linear programming; approximation algorithms
Organisational unit
09487 - Zenklusen, Rico / Zenklusen, Rico