• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

The Asymmetric Traveling Salesman Problem

Mattsson, Per January 2010 (has links)
This thesis is a survey on the approximability of the asymmetric traveling salesmanproblem with triangle inequality (ATSP).In the ATSP we are given a set of cities and a function that gives the cost of travelingbetween any pair of cities. The cost function must satisfy the triangle inequality, i.e.the cost of traveling from city A to city B cannot be larger than the cost of travelingfrom A to some other city C and then to B. However, we allow the cost function tobe asymmetric, i.e. the cost of traveling from city A to city B may not equal the costof traveling from B to A. The problem is then to find the cheapest tour that visit eachcity exactly once. This problem is NP-hard, and thus we are mainly interested in approximationalgorithms. We study the repeated cycle cover heuristic by Frieze et al. We alsostudy the Held-Karp heuristic, including the recent result by Asadpour et al. that givesa new upper bound on the integrality gap. Finally we present the result ofPapadimitriou and Vempala which shows that it is NP-hard to approximate the ATSP with a ratio better than 117/116.

Page generated in 0.0429 seconds