Back to search

Cal Poly

Empirical Comparsion of Traveling Salesperson Approximation Algorithms

Abstract

dc:description.abstract

The 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 × 6

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.calpoly.edu/theses/3344

Chain of custody

source
Harvested from
Cal Poly
Base URL
digitalcommons.calpoly.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Daijavad, Shayan. Empirical Comparsion of Traveling Salesperson Approximation Algorithms. https://digitalcommons.calpoly.edu/theses/3344