Competitive Analysis of Scheduling Problems and List Accessing Problems
- Competitive analysis is a well known method for analyzing online algorithms. Two online optimization problems, the scheduling problems and the list accessing problems, are considered in the thesis of Yida Zhu in the respect of this method. For both problems, several existing online and offline algorithms are studied. Their performances are compared with the performances of corresponding offline optimal algorithms. In particular, the list accessing algorithm BIT is carefully reviewed. The classical proof of its worst case performance get simplified by adapting the knowledge about the optimal offline algorithm. With regard to average case analysis, a new closed formula is developed to determine the performance of BIT on specific class of instances. All algorithm considered in this thesis are also implemented in Julia. Their empirical performances are studied and compared with each other directly.
Author: | Yida Zhu |
---|---|
URN: | urn:nbn:de:hbz:385-1-12884 |
DOI: | https://doi.org/10.25353/ubtr-xxxx-5db7-521e |
Referee: | Sven de Vries, Jan Pablo Burgard, Leonhard Frerick |
Advisor: | Sven de Vries, Jan Pablo Burgard |
Document Type: | Doctoral Thesis |
Language: | English |
Date of completion: | 2019/10/28 |
Publishing institution: | Universität Trier |
Granting institution: | Universität Trier, Fachbereich 4 |
Date of final exam: | 2019/10/02 |
Release Date: | 2019/11/07 |
GND Keyword: | Optimierung; Reihenfolgeproblem; competitive analysis |
Licence (German): | CC BY: Creative-Commons-Lizenz 4.0 International |