Abstract
dc:description.abstractThe traveling salesperson problem deals with optimizing the route a traveling sales- person might take to visit a set of places exactly once and return back to their starting point. The problem is NP-hard, and it is hard to approximate in general, but special cases have many approximation algorithms, which come with tradeoffs. In this thesis we compare the runtime, approximation ratio, and overall implementation complexity of two approximation algorithms for the Euclidean version of the problem, a classical 2-approximation algorithm and the multifragment heuristic. We run both algorithms on randomly generated point sets and real world data from TSPLIB. We find that despite a worse theoretical approximation ratio of O(log n), the multifragment heuristic empirically outperforms the 2-approximation both in terms of runtime and in terms of route length.
Degree
thesis:*- Name thesis:degree_name
- MS in Computer Science
- Discipline thesis:degree_discipline
- Computer Science
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Daijavad, Shayan
- Contributors dc:contributor
-
- Daniel Frishberg
- Computer Science
- College of Engineering
Subjects
dc:subject × 6Identifiers
dc:identifier.*- Repository record dc:identifier
- https://digitalcommons.calpoly.edu/theses/3344