|Approximation Algorithms for Automated Car Parking Systems|
|Organisatsiooni nimi||Algorithms & Theory|
|Kokkuvõte||This thesis is part of a larger project which controls robots in automated valet car parking systems (driver drops off his car, robots park it, robots retrieve it when demanded by owner). The robots are controlled by a central algorithm which aims to satisfy all car movements in the smallest amount of time.|
The starting point of this sub-project is a paper  on approximation algorithms for a related optimization problem.
The thesis can go two ways.
1. Coding only: understand the paper , adapt the algorithms in it, implement them in C++, integrate them into the existing software.
2. Some amount of proofs: The topic allows to reduce the coding part and add proofs to the thesis. What needs to be proved is NP-hardness of some problems, or approximation guarantees of algorithms.
|Lõputöö kaitsmise aasta||2016-2017|
|Juhendaja||Dirk Oliver Theis, Abdullah Makkeh|
|Nõuded kandideerijale||C++, interest in (coding) algorithms|