Reducing path TSP to TSP

DOI10.1145/3357713.3384256zbMath1489.68405arXiv1907.10376OpenAlexW3035754533MaRDI QIDQ5144892

Vera Traub, Jens Vygen, Rico Zenklusen

Publication date: 19 January 2021

Published in: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1907.10376

zbMATH Keywords

dynamic programmingtraveling salesman problemapproximation algorithms

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Dynamic programming (90C39) Approximation algorithms (68W25)

Related Items (6)

A 3/2-Approximation for the Metric Many-Visits Path TSP ⋮ Slightly improved upper bound on the integrality ratio for the \(s - t\) path TSP ⋮ Improving on best-of-many-Christofides for \(T\)-tours ⋮ A deterministic better-than-3/2 approximation algorithm for metric TSP ⋮ Polyhedral techniques in combinatorial optimization: matchings and tours ⋮ An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem

This page was built for publication: Reducing path TSP to TSP