Relative Worst-Order Analysis: A Survey

作者: Lene M. Favrholdt , Joan Boyar , Kim S. Larsen

DOI:

关键词:

摘要: Relative worst-order analysis is a technique for assessing the relative quality of online algorithms. We survey most important results obtained with this and compare it other measures.

参考文章(44)
Gabriel Moruz, Andrei Negoescu, None, Outperforming LRU via competitive analysis on parametrized inputs for paging symposium on discrete algorithms. pp. 1669- 1680 ,(2012) , 10.5555/2095116.2095248
Joan Boyar, Sushmita Gupta, Kim S. Larsen, Relative interval analysis of paging algorithms on access graphs Theoretical Computer Science. ,vol. 568, pp. 28- 48 ,(2015) , 10.1016/J.TCS.2014.11.035
Prabhakar Raghavan, A Statistical Adversary for On-line Algorithms. On-Line Algorithms. pp. 79- 84 ,(1991)
Ran El-Yaniv, Allan Borodin, Online Computation and Competitive Analysis ,(1998)
Juraj Hromkovič, Rastislav Královič, Richard Královič, Information complexity of online problems mathematical foundations of computer science. ,vol. 6281, pp. 24- 36 ,(2010) , 10.1007/978-3-642-15155-2_3
J. Boyar, K. S. Larsen, The Seat Reservation Problem Algorithmica. ,vol. 25, pp. 403- 417 ,(1996) , 10.1007/PL00009286
Joan Boyar, Martin R Ehmsen, Jens S Kohrt, Kim S Larsen, None, A theoretical comparison of LRU and LRU-K Acta Informatica. ,vol. 47, pp. 359- 374 ,(2010) , 10.1007/S00236-010-0123-6
Susanne Albers, Bernhard von Stengel, Ralph Werchner, A combined BIT and TIMESTAMP algorithm for the list update problem Information Processing Letters. ,vol. 56, pp. 135- 139 ,(1995) , 10.1016/0020-0190(95)00142-Y
Susanne Albers, Lene M. Favrholdt, Oliver Giel, On paging with locality of reference Journal of Computer and System Sciences. ,vol. 70, pp. 145- 175 ,(2005) , 10.1016/J.JCSS.2004.08.002
Joan Boyar, Lene M. Favrholdt, Scheduling Jobs on Grid Processors Algorithmica. ,vol. 57, pp. 819- 847 ,(2010) , 10.1007/S00453-008-9257-0