Analysis of a high-performance TSP solver on the GPU

DOI10.1145/3154835MaRDI QIDQ4577952zbMATH OpenOpenAlexWikidataFDO

Authors J. Robinson, Susan V. Vrbsky, Xiaoyan Hong, Brian P. Eddy

Publication date 6 August 2018

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3154835

zbMATH Keywords

TSPCUDAGPGPU2-opt\(k\)-swap

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms (68W40) Combinatorial optimization (90C27) Parallel algorithms in computer science (68W10)

Recommendations

• Multiple \(k\)-opt evaluation multiple \(k\)-opt moves with GPU high performance local search to large-scale traveling salesman problems
• scientific article; zbMATH DE number 1304530
• The traveling salesman problem: An overview of exact and approximate algorithms
• Generalized traveling salesman problem reduction algorithms
• Discrete heat transfer search for solving travelling salesman problem

Cites work

• scientific article; zbMATH DE number 1082106 (Why is no real title available?)
• A method for solving traveling-salesman problems
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• Introduction to algorithms.
• On the solution of traveling salesman problems
• Stability aspects of the traveling salesman problem based on \(k\)-best solutions
• TSPLIB—A Traveling Salesman Problem Library
• Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP

Cited in

(2)

• Solving the examination timetabling problem in GPUs
• A novel list-constrained randomized VND approach in GPU for the traveling thief problem

Describes a project that uses

Uses Software

• TSPLIB
• CUDA
• OpenCL

This page was built for publication: Analysis of a high-performance TSP solver on the GPU

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