Options
A (3/2 + 1/e)-Approximation algorithm for ordered TSP
Citation Link: https://doi.org/10.15480/882.13294
Publikationstyp
Conference Paper
Date Issued
2024-08-28
Sprache
English
TORE-DOI
First published in
Number in series
317
Article Number
1
Citation
International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2024)
Publisher DOI
Scopus ID
Publisher
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN
978-3-9597-7348-5
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.
Subjects
Travelling Salesperson Problem
Precedence constraints
Linear programming
Approximation algorithms
DDC Class
519: Applied Mathematics, Probabilities
518: Numerical Analysis
Publication version
publishedVersion
Loading...
Name
LIPIcs.APPROX-RANDOM.2024.1.pdf
Type
Main Article
Size
911.63 KB
Format
Adobe PDF