A Parallel Implementation of A Greedy TSP Algorithm

Simple item page
dc.contributor.advisorBurtscher, Martin
dc.contributor.authorGonzalez, Andres
dc.contributor.committeeMemberPeng, Wuxu
dc.contributor.committeeMemberYang, Kecheng
dc.date.accessioned2020-11-16T18:26:06Z
dc.date.available2020-11-16T18:26:06Z
dc.date.issued2020-11
dc.description.abstractThe Traveling Salesman Problem has often been used as an exploration ground for building heuristics to calculate the shortest path of a complete graph that traverse every vertex exactly once. This has a number of important practical applications. Since it is an NP-hard problem, many heuristics have been proposed to obtain near-optimal solutions in polynomial time. The heuristic explored in this study is based on Kruskal’s algorithm, where the edges of a graph are sorted in non-decreasing order. The smallest edges that meet the eligibility criteria are included in the path until a tour that includes all vertices has been constructed. Whether an edge meets the criteria depends on which smaller edges have been inserted. This makes the algorithm difficult to parallelize. I combined previously published with new parallelization techniques and implemented the algorithm in OpenMP and CUDA. The resulting GPU code is very fast, taking just 0.06 seconds to process a graph with 11,849 vertices and 70,193,476 edges. This is approximately 8 times faster than the serial CPU implementation and has a solution quality that is within 18% of the optimal. Compared to the optimal solver CONCORDE, my code is 1,206,302 times faster.
dc.description.departmentComputer Science
dc.formatText
dc.format.extent81 pages
dc.format.medium1 file (.pdf)
dc.identifier.citationGonzalez, A. (2020). <i>A parallel implementation of a greedy TSP algorithm</i> (Unpublished thesis). Texas State University, San Marcos, Texas.
dc.identifier.urihttps://hdl.handle.net/10877/12922
dc.language.isoen
dc.subjectTSP
dc.subjectTraveling Salesman Problem
dc.subject.lcshElectronic data processing--Distributed processing
dc.subject.lcshComputer algorithms
dc.subject.lcshParallel programming (Computer science)
dc.titleA Parallel Implementation of A Greedy TSP Algorithm
dc.typeThesis
thesis.degree.departmentComputer Science
thesis.degree.disciplineComputer Science
thesis.degree.grantorTexas State University
thesis.degree.levelMasters
thesis.degree.nameMaster of Science

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
GONZALEZ-THESIS-2020.pdf
Size:
2.84 MB
Format:
Adobe Portable Document Format
Download

License bundle

Now showing 1 - 2 of 2
No Thumbnail Available
Name:
PROQUEST_LICENSE.txt
Size:
4.53 KB
Format:
Plain Text
Description:
Download
No Thumbnail Available
Name:
LICENSE.txt
Size:
2.97 KB
Format:
Plain Text
Description:
Download

Collections

Graduate Theses and Dissertations