4/3-Approximation of Graphic TSP

2023/05/09 by Ali Çivril, Çivril, Ali
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Algorithm #Approximation algorithm #Artificial intelligence #Combinatorics #Computer science #Degree (music) #Discrete mathematics #Enhanced Data Rates for GSM Evolution #Factor-critical graph #Graph #Graph power #Line graph #Matching (statistics) #Mathematics #Optimization and Packing Problems #Physics #Travelling salesman problem #Vehicle Routing Optimization Methods #cs.DS

paper · pdf · doi:10.48550/arxiv.2305.05411

openalex publication_date 2023/05/09 · openalex created_date 2023/05/12 · openalex updated_date 2026/08/05

Abstract

We describe a (4)/(3)-approximation algorithm for the traveling salesman problem in which the distances between points are induced by graph-theoretical distances in an unweighted graph. The algorithm is based on finding a minimum cost perfect matching on the odd degree vertices of a carefully computed 2-edge-connected spanning subgraph.

Related

• Approximating Graphic TSP by Matchings
• Parameterized Approximation Algorithms for TSP on Non-Metric Graphs
• A 4/5 - Approximation Algorithm for the Maximum Traveling Salesman Problem
• An LP-based 3/2-approximation algorithm for the graphic s-t path TSP
• Beating the integrality ratio for s-t-tours in graphs