论文标题
一种新颖的移动到五或杂物位置（MFLP）在线列表更新算法
A Novel Move-To-Front-or-Logarithmic Position (MFLP) Online List Update Algorithm
论文作者
论文摘要
在本文中，我们提出了一个新颖的在线确定性列表更新算法，称为“转到fotront-orgarithmitic”位置（MFLP）。相对于静态最佳离线算法，我们提出的算法MFLP的竞争比为2，而MFLP对于较小的列表没有竞争力。我们还表明，对于动态最佳离线算法，MFLP具有2个竞争力。我们的结果为基于竞争性而不是竞争性的在线算法进行分类开辟了新的工作方向。
In this paper we propose a novel online deterministic list update algorithm known as Move-To-Front-or-Logarithmic Position (MFLP). Our proposed algorithm MFLP achieves a competitive ratio of 2 for larger list with respect to static optimum offline algorithm, whereas MFLP is not competitive for smaller list. We also show that MFLP is 2 competitive with respect to dynamic optimum offline algorithm. Our results open up a new direction of work towards classifying the online algorithms based on competitive and not competitive.
