{"id":{"repo_id":"calpoly","oai_identifier":"oai:digitalcommons.calpoly.edu:theses-5043"},"canonical_url":"https://search.ndltd.org/etd/calpoly/oai:digitalcommons.calpoly.edu:theses-5043","repository":{"repo_id":"calpoly","name":"Cal Poly","base_url":"https://digitalcommons.calpoly.edu/do/oai/"},"display":{"title":"Empirical Comparsion of Traveling Salesperson Approximation Algorithms","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Daijavad, Shayan"],"institution":null,"degree_name":"MS in Computer Science","degree_level":null,"degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Daniel Frishberg","Computer Science","College of Engineering"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-11-19T07:12:58Z","subjects":["Traveling salesperson","multifragment heuristic","2-approximation","algorithm analysis","nearest neighbor chain","Theory and Algorithms"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.calpoly.edu/theses/3344","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://digitalcommons.calpoly.edu/theses/3344","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://digitalcommons.calpoly.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adigitalcommons.calpoly.edu%3Atheses-5043","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Daniel Frishberg","Computer Science","College of Engineering"]},{"key":"dc:creator","label":"Author","values":["Daijavad, Shayan"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2026-06-12T07:00:00Z"]},{"key":"dc:date.created","label":"Dc Date Created","values":["2026-06-01T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_name","label":"Degree Name","values":["MS in Computer Science"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Traveling salesperson","multifragment heuristic","2-approximation","algorithm analysis","nearest neighbor chain","Theory and Algorithms"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.calpoly.edu/theses/3344"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:title","label":"Title","values":["Empirical Comparsion of Traveling Salesperson Approximation Algorithms"]}]}],"canonical_facts":{"dc:contributor":["Daniel Frishberg","Computer Science","College of Engineering"],"dc:creator":["Daijavad, Shayan"],"dc:date.available":["2026-06-12T07:00:00Z"],"dc:date.created":["2026-06-01T07:00:00Z"],"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."],"dc:identifier":["https://digitalcommons.calpoly.edu/theses/3344"],"dc:subject":["Traveling salesperson","multifragment heuristic","2-approximation","algorithm analysis","nearest neighbor chain","Theory and Algorithms"],"dc:title":["Empirical Comparsion of Traveling Salesperson Approximation Algorithms"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_name":["MS in Computer Science"]},"updated_at":"2026-11-19T07:12:58Z"}