An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality

DOI10.1016/j.ipl.2015.06.003zbMath1331.68295arXiv1412.6755OpenAlexW1480102953MaRDI QIDQ2353642

Tobias Mömke

Publication date: 15 July 2015

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

TSPalgorithmsanalysis of algorithmsdesign of algorithmsgraph algorithmsapproximation algorithmsrelaxed triangle inequality

Mathematics Subject Classification ID

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

Related Items (5)

On the approximability of the single allocation \(p\)-hub center problem with parameterized triangle inequality ⋮ Approximability and inapproximability of the star \(p\)-hub center problem with parameterized triangle inequality ⋮ A Modern View on Stability of Approximation ⋮ A 4-approximation algorithm for the TSP-path satisfying a biased triangle inequality ⋮ Approximation algorithms for the \(p\)-hub center routing problem in parameterized metric graphs

Cites Work

• Unnamed Item
• Performance guarantees for the TSP with a parameterized triangle inequality
• Shorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphs
• Approximation algorithms for multi-dimensional assignment problems with decomposable costs
• Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
• \(\frac{13}{9}\)-approximation for graphic TSP
• Degree bounded matroids and submodular flows
• On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
• Approximating minimum bounded degree spanning trees to within one of optimal
• Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
• Matching, Euler tours and the Chinese postman
• A Randomized Rounding Approach to the Traveling Salesman Problem
• Approximating Graphic TSP by Matchings
• The Traveling-Salesman Problem and Minimum Spanning Trees

This page was built for publication: An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality