The asymmetric traveling salesman path LP has constant integrality ratio

DOI10.1007/978-3-030-17953-3_22zbMath1450.90043arXiv1808.06542OpenAlexW2951508903WikidataQ126624587 ScholiaQ126624587MaRDI QIDQ5918918

Vera Traub, Jens Vygen, Anna Köhne

Publication date: 28 August 2020

Published in: Mathematical Programming. Series A. Series B, Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

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

zbMATH Keywords

asymmetric traveling salesman problemlinear programming relaxationsintegrality gap

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (3)

A constant-factor approximation for directed latency in quasi-polynomial time ⋮ A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time ⋮ An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem

Cites Work

• Unnamed Item
• Asymmetric Traveling Salesman Path and Directed Latency Problems
• An Improved Integrality Gap for Asymmetric TSP Paths
• The Directed Minimum Latency Problem
• Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs
• A constant-factor approximation algorithm for the asymmetric traveling salesman problem
• On the Integrality Ratio for the Asymmetric Traveling Salesman Problem
• Optimum branchings

This page was built for publication: The asymmetric traveling salesman path LP has constant integrality ratio