---- dataentry project ----
title : Approximation Algorithms for the Undirected Travelling Salesman Problem
contactname: Ola Svensson
contactmail_mail: ola.svensson@epfl.ch
contacttel: 021-693-1204
contactroom: BC 128
type : bachelor semester
state : completed
created_dt : 2011-09-17
taken_dt :  
completed_dt : 2012-01-16
by : Aleksandar Markovic
output_media : 
table : projects
======
template:datatemplates:project
----

{{:en:projects:bachelor_semester:reportealeksandarmarkovic.pdf|Final report}}

We present an overview of known approximation algorithms and
linear programming relaxations of the Undirected Travelling Salesman
Problem with the triangle inequality.

In particular, we review the classical algorithm by Christofides and
explain how it upper bounds the integrality gap of the considered linear
programming relaxation.

We also complement this by presenting better upper bounds for
specific cases, such as subcubic graphs in the unweighed shortest path
metric and two 5-cycles connected by five paths in a general metric.