A Polynomial-Time Approximation Scheme for Traveling Salesman Problem with Neighborhoods Over Parallel Line Segments of Similar Length

• Author / Creator

  Ghaseminia, Benyamin

• In this thesis, we consider the Traveling Salesman Problem with Neighborhoods (TSPN) on the Euclidean plane, and present a Polynomial-Time Approximation Scheme (PTAS) when the neighborhoods are parallel line segments with lengths between [1, λ] for any constant value λ.In TSPN (which generalizes classic TSP), each client represents a set (or neighborhood) of points in a metric and the goal is to find a minimum cost TSP tour that visits at least one point from each client set. In the Euclidean setting, each neighborhood is a region on the plane.TSPN is significantly more difficult than classic TSP even in the Euclidean setting.A notable case of TSPN is when each neighborhood is a line segment. Although there are PTAS's for when neighborhoods are fat objects (with limited overlap), TSPN over line segments is APX-hard even if all the line segments have unit length. For parallel (unit) line segments, the best approximation factor is 3√2 from 20 years ago.The PTAS we present, settles the approximability of this case of the problem. Our algorithm finds a (1 + ε)-factor approximation for an instance of the problem with n segments with lengths in [1, λ] in time n^O(λ/ε^3).

• Subjects / Keywords

  • Approximation Algorithms
  • TSP
  • PTAS
  • TSPN
  • Traveling Salesman

• Graduation date

  Fall 2024

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/r3-k4y1-4a20

• License

  This thesis is made available by the University of Alberta Library with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.