An experimental evaluation of the best-of-many Christofides' algorithm for the traveling salesman problem

DOI10.1007/s00453-017-0293-5zbMath1372.90090arXiv1506.07776OpenAlexW1939273335MaRDI QIDQ2408163

Kyle Genova, David P. Williamson

Publication date: 10 October 2017

Published in: Algorithmica, Algorithms - ESA 2015 (Search for Journal in Brave)

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

zbMATH Keywords

maximum entropytraveling salesman problemapproximation algorithmsChristofides' algorithmChristofides algorithm

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (6)

Better s-t-Tours by Gao Trees ⋮ An experimental evaluation of the best-of-many Christofides' algorithm for the traveling salesman problem ⋮ Fractional decomposition tree algorithm: a tool for studying the integrality gap of integer programs ⋮ Reassembling Trees for the Traveling Salesman ⋮ Better \(s-t\)-tours by Gao trees ⋮ IntraClusTSP -- an incremental intra-cluster refinement heuristic algorithm for symmetric travelling salesman problem

Uses Software

• TSPLIB
• Gurobi
• Concorde
• Blossom V
• Eigen
• Triangle
• KONECT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Blossom V: A new implementation of a minimum cost perfect matching algorithm
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Deterministic \(\tilde O(nm)\) time edge-splitting in undirected graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• \(\frac{13}{9}\)-approximation for graphic TSP
• An experimental evaluation of the best-of-many Christofides' algorithm for the traveling salesman problem
• Reassembling Trees for the Traveling Salesman
• A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs
• Removing and Adding Edges for the Traveling Salesman Problem
• Better s-t-Tours by Gao Trees
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• TSPLIB—A Traveling Salesman Problem Library
• On some connectivity properties of Eulerian graphs
• Eight-Fifth Approximation for the Path TSP
• Improving christofides' algorithm for the s-t path TSP
• A Randomized Rounding Approach to the Traveling Salesman Problem
• Approximating Graphic TSP by Matchings
• On the Metric $s$--$t$ Path Traveling Salesman Problem
• The Traveling-Salesman Problem and Minimum Spanning Trees
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem

This page was built for publication: An experimental evaluation of the best-of-many Christofides' algorithm for the traveling salesman problem