Yida Zhu

• 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.