{"id":{"repo_id":"mcmaster","oai_identifier":"oai:macsphere.mcmaster.ca:11375/9111"},"canonical_url":"https://search.ndltd.org/etd/mcmaster/oai:macsphere.mcmaster.ca:11375/9111","repository":{"repo_id":"mcmaster","name":"McMaster University","base_url":"https://macsphere.mcmaster.ca/server/oai/request"},"display":{"title":"A Primal-Dual Heuristic for the Traveling Salesman Problem","abstract":"<p>In this thesis we provide a Linear Programming (LP) formulation and a heuristic for the symmetric Traveling Salesman Problem (TSP) on certain complete graphs having the triangle inequality.</p> <p>TSP models cities and their pairwise connections as vertices and edges between them in a graph. The distances are represented by cost values on edges, and the goal is to find a minimum weight tour that visits every vertex exactly once. In symmetric cases all connections are undirected - both directions have the same cost. This problem is NP-Complete, so there is no polynomial time exact algorithm known for it.</p> <p>We present three major points in this thesis. Inspired by an LP formulation of perfect matching, we develop a relaxation for TSP, and prove that our relaxation is equivalent to the path form of the well-known Held-Karp formulation. Then, based on this relaxation we construct a heuristic, hoping it can approach a constant factor 4/3 of the optimal objective value given by the LP relaxation. At last, we adopt the matroid idea. It's already known that TSP can be modeled as minimum weight intersection of three matroids, but solving that is also NP-Complete. Vle present in this thesis the attempt to approach it using only two matroids, and analyze the difficulty.</p>","abstract_html":"&lt;p&gt;In this thesis we provide a Linear Programming (LP) formulation and a heuristic for the symmetric Traveling Salesman Problem (TSP) on certain complete graphs having the triangle inequality.&lt;/p&gt; &lt;p&gt;TSP models cities and their pairwise connections as vertices and edges between them in a graph. The distances are represented by cost values on edges, and the goal is to find a minimum weight tour that visits every vertex exactly once. In symmetric cases all connections are undirected - both directions have the same cost. This problem is NP-Complete, so there is no polynomial time exact algorithm known for it.&lt;/p&gt; &lt;p&gt;We present three major points in this thesis. Inspired by an LP formulation of perfect matching, we develop a relaxation for TSP, and prove that our relaxation is equivalent to the path form of the well-known Held-Karp formulation. Then, based on this relaxation we construct a heuristic, hoping it can approach a constant factor 4/3 of the optimal objective value given by the LP relaxation. At last, we adopt the matroid idea. It&#x27;s already known that TSP can be modeled as minimum weight intersection of three matroids, but solving that is also NP-Complete. Vle present in this thesis the attempt to approach it using only two matroids, and analyze the difficulty.&lt;/p&gt;","abstract_has_math":false,"creators":["Ma, Xiaoxi"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Computing and Software","school":null,"contributors":[],"advisors":["Karakostas, George"],"committee_chairs":[],"committee_members":[],"year":2010,"date_issued":"2010","date_published":"2010","updated_at":"2026-11-18T19:33:25Z","subjects":["Computing and Software","Computer Engineering"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://doi.org/10.71548/14050"],"render_values":[{"text":"https://doi.org/10.71548/14050","href":"https://doi.org/10.71548/14050","code":true}]},{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["opendissertations/4263","5282","2035678"],"render_values":[{"text":"opendissertations/4263","href":null,"code":true},{"text":"5282","href":null,"code":true},{"text":"2035678","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/11375/9111","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"http://hdl.handle.net/11375/9111","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://macsphere.mcmaster.ca/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Amacsphere.mcmaster.ca%3A11375%2F9111","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Karakostas, George"]},{"key":"dc:contributor.department","label":"Department","values":["Computing and Software"]},{"key":"dc:creator","label":"Author","values":["Ma, Xiaoxi"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2014-06-18T16:45:39Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2014-06-18T16:45:39Z"]},{"key":"dc:date.created","label":"Dc Date Created","values":["2011-05-27"]},{"key":"dc:date.issued","label":"Date","values":["2010"]},{"key":"dc:type","label":"Dc Type","values":["thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computing and Software","Computer Engineering"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["opendissertations/4263","5282","2035678"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/11375/9111","https://doi.org/10.71548/14050"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["<p>In this thesis we provide a Linear Programming (LP) formulation and a heuristic for the symmetric Traveling Salesman Problem (TSP) on certain complete graphs having the triangle inequality.</p> <p>TSP models cities and their pairwise connections as vertices and edges between them in a graph. The distances are represented by cost values on edges, and the goal is to find a minimum weight tour that visits every vertex exactly once. In symmetric cases all connections are undirected - both directions have the same cost. This problem is NP-Complete, so there is no polynomial time exact algorithm known for it.</p> <p>We present three major points in this thesis. Inspired by an LP formulation of perfect matching, we develop a relaxation for TSP, and prove that our relaxation is equivalent to the path form of the well-known Held-Karp formulation. Then, based on this relaxation we construct a heuristic, hoping it can approach a constant factor 4/3 of the optimal objective value given by the LP relaxation. At last, we adopt the matroid idea. It's already known that TSP can be modeled as minimum weight intersection of three matroids, but solving that is also NP-Complete. Vle present in this thesis the attempt to approach it using only two matroids, and analyze the difficulty.</p>"]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Master of Science (MS)"]},{"key":"dc:title","label":"Title","values":["A Primal-Dual Heuristic for the Traveling Salesman Problem"]},{"key":"others:access_status","label":"Others Access Status","values":["open.access"]}]}],"canonical_facts":{"dc:contributor.advisor":["Karakostas, George"],"dc:contributor.department":["Computing and Software"],"dc:creator":["Ma, Xiaoxi"],"dc:date.accessioned":["2014-06-18T16:45:39Z"],"dc:date.available":["2014-06-18T16:45:39Z"],"dc:date.created":["2011-05-27"],"dc:date.issued":["2010"],"dc:description.abstract":["<p>In this thesis we provide a Linear Programming (LP) formulation and a heuristic for the symmetric Traveling Salesman Problem (TSP) on certain complete graphs having the triangle inequality.</p> <p>TSP models cities and their pairwise connections as vertices and edges between them in a graph. The distances are represented by cost values on edges, and the goal is to find a minimum weight tour that visits every vertex exactly once. In symmetric cases all connections are undirected - both directions have the same cost. This problem is NP-Complete, so there is no polynomial time exact algorithm known for it.</p> <p>We present three major points in this thesis. Inspired by an LP formulation of perfect matching, we develop a relaxation for TSP, and prove that our relaxation is equivalent to the path form of the well-known Held-Karp formulation. Then, based on this relaxation we construct a heuristic, hoping it can approach a constant factor 4/3 of the optimal objective value given by the LP relaxation. At last, we adopt the matroid idea. It's already known that TSP can be modeled as minimum weight intersection of three matroids, but solving that is also NP-Complete. Vle present in this thesis the attempt to approach it using only two matroids, and analyze the difficulty.</p>"],"dc:description.degree":["Master of Science (MS)"],"dc:identifier.other":["opendissertations/4263","5282","2035678"],"dc:identifier.uri":["http://hdl.handle.net/11375/9111","https://doi.org/10.71548/14050"],"dc:subject":["Computing and Software","Computer Engineering"],"dc:title":["A Primal-Dual Heuristic for the Traveling Salesman Problem"],"dc:type":["thesis"],"others:access_status":["open.access"]},"updated_at":"2026-11-18T19:33:25Z"}