The asymmetric traveling salesman path LP has constant integrality ratio

2018/08/20 by Anna Köhne, Köhne, Anna, Vera Traub +3 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Vehicle Routing Optimization Methods #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.1808.06542

openalex publication_date 2018/08/20 · arxiv created 2018/10/01 · arxiv updated 2018/10/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that the classical LP relaxation of the asymmetric traveling salesman path problem (ATSPP) has constant integrality ratio. If ρ_ATSP and ρ_ATSPP denote the integrality ratios for the asymmetric TSP and its path version, then ρ_ATSPP≤ 4ρ_ATSP-3. We prove an even better bound for node-weighted instances: if the integrality ratio for ATSP on node-weighted instances is ρ_ATSP^NW, then the integrality ratio for ATSPP on node-weighted instances is at most 2ρ_ATSP^{\text NW}-1. Moreover, we show that for ATSP node-weighted instances and unweighted digraph instances are almost equivalent. From this we deduce a lower bound of 2 on the integrality ratio of unweighted digraph instances.

Cited by

• A Constant-Factor Approximation for Directed Latency

Related

• Approximating ATSP by Relaxing Connectivity
• On Integrality Ratios for Asymmetric TSP in the Sherali-Adams Hierarchy
• A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
• Asymmetric Traveling Salesman Path and Directed Latency Problems
• An Improved Integrality Gap for Asymmetric TSP Paths