Back to search

McMaster University

A Primal-Dual Heuristic for the Traveling Salesman Problem

Abstract

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>

Degree

thesis:*
Department dc:contributor.department
Computing and Software
Year dc:date.issued
2010

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Ma, Xiaoxi
Advisor dc:contributor.advisor
  • Karakostas, George

Subjects

dc:subject × 2

Identifiers

dc:identifier.*
Dc Identifier Other
opendissertations/4263
5282
2035678

Chain of custody

source
Harvested from
McMaster University
Base URL
macsphere.mcmaster.ca/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Ma, Xiaoxi. A Primal-Dual Heuristic for the Traveling Salesman Problem. 2010. http://hdl.handle.net/11375/9111