arvutiteaduse instituudi lõputööde teemade register

The State of the Union: Quickly Finding Gaps in Unions of High-Dimensional Rectangles
Organisatsiooni nimiAlgorithms & Theory
KokkuvõteThis is a proof-oriented computational geometry topic. Given as input a set of axis-parallel d-dimensional small boxes contained in a large box, decide if they cover the large box, or leave points uncovered.
The goal of the thesis is to:
1. review the available literature on the problem;
2. determine its complexity (NP-hardness)
3. produce approximation algorithms and prove performance guarantees
4. code the algorithms.
Lõputöö kaitsmise aasta2016-2017
JuhendajaDirk Oliver Theis
Suhtlemiskeel(ed)inglise keel
Nõuded kandideerijaleAnalysis of algorithms
Tase Magister
Märksõnad #tcs
Kandideerimise kontakt
Nimi Dirk Oliver Theis