A Novel Way to Analyze Competiive Performance of Online Algorithms
Jiping Tao, Zhijun Chao, Yugeng Xi, Oscar Castillo, Chris Douglas, DD Feng, Anna So Youn Lee, 陶继平 · 2009
Abstract |A competitive analysis method for on-line algorithms is developed based on the idea of in-stance transformation. The method is applied on asingle machine online scheduling problem where anassumption is made that the longest processing timeamong the jobs in any instance is not longer than aconstant, say ° , times the shortest processing time.An online algorithm is designed and its competitiveratio is proven to be 1 + °i 11+ p 1+ ° ( °i 1) by the proposedanalysis method. Keywords: online algorithm, competitive analysis, sin-gle machine scheduling, total completion time 1 Introduction Many scheduling problems are intrinsically online in thatthey require immediate decisions to be made in real time.Ready-made examples include CPU scheduling in themulti-processor operating system and routing in commu-nications networks. The corresponding algorithms solv-ing these online problems have to be online. In contrastto the o†ine version, an online algorithm must producea sequence of decisions based on past events without anyinformation about the future. The lack of knowledge ofthe future does generally not guarantee the optimality ofthe obtained schedule. Thus a natural issue is how toevaluate difierent online algorithms that solve the prob-lem.A widely used approach to evaluate online algorithms iscompetitive analysis, where the quality of an online algo-rithm on each input instance is measured by comparingits performance with that of the optimal o†ine algorithm.An online algorithm is called