A 3/4 differential approximation algorithm for traveling salesman problem

DOI10.1007/978-3-031-20350-3_19MaRDI QIDQ6111960zbMATH OpenOpenAlexFDO

Authors Yuki Amano, Kazuhisa Makino

Publication date 4 August 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsdifferential approximationtraveling salesman problem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: In this paper, we consider differential approximability of the traveling salesman problem (TSP). We show that TSP is $3/4$-differential approximable, which improves the currently best known bound $3/4-O(1/n)$ due to Escoffier and Monnot in 2008, where $n$ denotes the number of vertices in the given graph.

Cites work

• z-approximations
• A (slightly) improved approximation algorithm for metric TSP
• A 3/4 differential approximation algorithm for traveling salesman problem
• A better differential approximation ratio for symmetric TSP
• A Dynamic Programming Approach to Sequencing Problems
• An Algorithm for the Traveling Salesman Problem
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• Approximation algorithms for the traveling salesman problem
• Approximation hardness of Travelling Salesman via weighted amplifiers
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES
• Differential approximation results for the traveling salesman and related problems
• Differential approximation results for the traveling salesman problem with distances 1 and 2
• Dynamic Programming Treatment of the Travelling Salesman Problem
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• scientific article; zbMATH DE number 1670809 (Why is no real title available?)
• scientific article; zbMATH DE number 1219584 (Why is no real title available?)
• scientific article; zbMATH DE number 2064404 (Why is no real title available?)
• scientific article; zbMATH DE number 3895002 (Why is no real title available?)
• Large traveling salesman problems arising from experiments in X-ray crystallography: A preliminary report on computation
• On an approximation measure founded on the links between optimization and polynomial approximation theory
• Optimal control of plotting and drilling machines: A case study
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• The traveling salesman problem and its variations

Cited in

(6)

• An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem
• A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
• scientific article; zbMATH DE number 1839451 (Why is no real title available?)
• A 4/3-approximation algorithm for half-integral cycle cut instances of the TSP
• A 3/4 differential approximation algorithm for traveling salesman problem
• A 3/4 differential approximation algorithm for traveling salesman problem

This page was built for publication: A 3/4 differential approximation algorithm for traveling salesman problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6111960)