• search hit 14 of 1006
Back to Result List

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.

Download full text files

Export metadata

Metadaten
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):License LogoCC BY: Creative-Commons-Lizenz 4.0 International

$Rev: 13581 $