This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
en:projects:bachelor_semester:mark11 [2012/02/15 10:53] osven |
en:projects:bachelor_semester:mark11 [2016/06/23 11:26] (current) |
||
|---|---|---|---|
| Line 6: | Line 6: | ||
| contactroom: BC 128 | contactroom: BC 128 | ||
| type : bachelor semester | type : bachelor semester | ||
| - | status : completed | + | state : completed |
| created_dt : 2011-09-17 | created_dt : 2011-09-17 | ||
| taken_dt : | taken_dt : | ||
| Line 17: | Line 17: | ||
| ---- | ---- | ||
| - | {{:en:projects:bachelor_semester:rapportealeksandarmarkovic.pdf|Final report}} | + | {{:en:projects:bachelor_semester:reportealeksandarmarkovic.pdf|Final report}} |
| We present an overview of known approximation algorithms and | We present an overview of known approximation algorithms and | ||
| linear programming relaxations of the Undirected Travelling Salesman | linear programming relaxations of the Undirected Travelling Salesman | ||
| Problem with the triangle inequality. | Problem with the triangle inequality. | ||
| + | |||
| In particular, we review the classical algorithm by Christofides and | In particular, we review the classical algorithm by Christofides and | ||
| explain how it upper bounds the integrality gap of the considered linear | explain how it upper bounds the integrality gap of the considered linear | ||
| programming relaxation. | programming relaxation. | ||
| + | |||
| We also complement this by presenting better upper bounds for | We also complement this by presenting better upper bounds for | ||
| specific cases, such as subcubic graphs in the unweighed shortest path | specific cases, such as subcubic graphs in the unweighed shortest path | ||