Title: approximation algorithms and hardness
results for Traveling Salesman Problem
Speaker: Manjanna Basappa
Date: November 20, 2015
Time: 11:30 AM
Venue: Discussion Room
ABSTRACT: The Travelling Salesman Prolem (TSP) is one of the most well studied combinatorial optimization problems. The traveling salesman problem consists of a salesman and a set of cities. The salesman has to visit each one of the cities starting from a certain one (e.g. the hometown) and returning to the same city. The challenge of the problem is that the traveling salesman wants to minimize the total length of the trip. In general the TSP problem can be modelled as complete weighted graph where vertices represent the cities and weights of the edges represent the length/cost of routes between cities. In this talk we discuss some approximation algorithms for TSP in metric space and it's lower bounds.