Comparison of approximation algorithms for the travelling salesperson problem on semimetric graphs

arXiv2108.13070MaRDI QIDQ6376317FDOQ6376317

Mateusz Krukowski, Filip Turoboś

Publication date: 30 August 2021

Abstract: The aim of the paper is to compare different approximation algorithms for the travelling salesperson problem. We pick the most popular and widespread methods known in the literature and contrast them with a novel approach (the polygonal Christofides algorithm) described in our previous work. The paper contains a brief summary of theory behind the algorithms and culminates in a series of numerical simulations (or "experiments"), whose purpose is to determine "the best" approximation algorithm for the travelling salesperson problem.

This page was built for publication: Comparison of approximation algorithms for the travelling salesperson problem on semimetric graphs

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