Approximation Algorithms for Automated Car Parking Systems
Organization
Algorithms & Theory
Abstract
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 [1] on approximation algorithms for a related optimization problem.
The thesis can go two ways.
1. Coding only: understand the paper [1], 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.
The starting point of this sub-project is a paper [1] on approximation algorithms for a related optimization problem.
The thesis can go two ways.
1. Coding only: understand the paper [1], 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.
Graduation Theses defence year
2016-2017
Supervisor
Dirk Oliver Theis, Abdullah Makkeh
Spoken language (s)
English
Requirements for candidates
C++, interest in (coding) algorithms
Level
Bachelor, Masters
Keywords
Application of contact
Name
Abed Makkeh
Phone
E-mail
Full Document