DROPS

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.1

A (3/2 + 1/e)-Approximation Algorithm for Ordered TSP

Authors: Susanne Armbruster, Matthias Mnich, and Martin Nägele

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

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.

Cite as

Susanne Armbruster, Matthias Mnich, and Martin Nägele. A (3/2 + 1/e)-Approximation Algorithm for Ordered TSP. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{armbruster_et_al:LIPIcs.APPROX/RANDOM.2024.1,
  author =	{Armbruster, Susanne and Mnich, Matthias and N\"{a}gele, Martin},
  title =	{{A (3/2 + 1/e)-Approximation Algorithm for Ordered TSP}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{1:1--1:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.1},
  URN =		{urn:nbn:de:0030-drops-209943},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.1},
  annote =	{Keywords: Travelling Salesperson Problem, precedence constraints, linear programming, approximation algorithms}
}

Search Results

Documents authored by Nägele, Martin

A (3/2 + 1/e)-Approximation Algorithm for Ordered TSP

Abstract

Cite as

Thanks for your feedback!

Could not send message