This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
|
en:projects:bachelor_semester:mark11 [2012/02/15 10:51] osven created |
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 | ||
| + | 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. | ||
| - | This project is devoted to understand one of the key algorithm of modern discrete mathematics. The LLL algorithm is today a standard tool to deal with lattices and is used in problems from pure and applied mathematics. You will be asked | ||
| - | * to understand how the algorithm is working, | ||
| - | * study some of its applications (factoring polynomials, linear algebra over the integer ring, application to coding theory) | ||
| - | * implement them by yourself. | ||
| - | Prerequisites: | ||
| - | * Good mathematical aptitude (Algebra and number theory especially) | ||