On the competitiveness of the move-to-front rule

被引：10
|
作者：
Martínez, C [1 ]
Roura, S [1 ]
机构：
[1] Univ Politecn Cataluna, Dept Llenguages & Sistemes Informat, E-08034 Barcelona, Spain
来源：
THEORETICAL COMPUTER SCIENCE | 2000年 / 242卷 / 1-2期
关键词：
competitive analysis; on-line algorithms; list update problem; move-to-front rule;
D O I：
10.1016/S0304-3975(98)00264-3
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We consider the list access problem and show that one questionable assumption in the original cost model presented by Sleator and Tarjan (1985) and subsequent literature allowed for several competitiveness; results of the move-to-front rule (MTF). We present an off-line algorithm for the list access problem and prove that, under a. more realistic cost model, no on-line algorithm can be c-competitive for any constant c, MTT: included. (C) 2000 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：313 / 325
页数：13
相关论文
共 50 条
  • [41] ADVANCES IN ENANTIOSELECTIVE TECHNOLOGY MOVE ACROSS A BROAD FRONT
    STINSON, SC
    CHEMICAL & ENGINEERING NEWS, 1995, 73 (17) : 37 - 40
  • [42] Which therapies will move to the front line for multiple myeloma?
    Cejalvo, Maria J.
    de la Rubia, Javier
    EXPERT REVIEW OF HEMATOLOGY, 2017, 10 (05) : 383 - 392
  • [43] Bjorken sum rule and perturbative QCD frontier on the move
    Pasechnik, Roman S.
    Shirkov, Dmitry V.
    Teryaev, Oleg V.
    PHYSICAL REVIEW D, 2008, 78 (07):
  • [44] THE 50-MOVE RULE ADAPTED .1.
    MEDNIS, E
    ICCA JOURNAL, 1989, 12 (02): : 123 - 123
  • [45] Modification rule of monodromies in an R2-move
    Hayano, Kenta
    ALGEBRAIC AND GEOMETRIC TOPOLOGY, 2014, 14 (04): : 2181 - 2222
  • [46] CLINICAL TRIALS Experimental Cancer Therapies Move to the Front Line
    Couzin-Frankel, Jennifer
    SCIENCE, 2012, 335 (6066) : 282 - 283
  • [47] Free movement of persons and the wholly internal rule: Time to move on?
    Shuibhne, NN
    COMMON MARKET LAW REVIEW, 2002, 39 (04): : 731 - 771
  • [48] Robust Active Front End Approach in Crane Applications for Port Competitiveness
    Sladic, Sasa
    Kolich, Damir
    Zigulic, Roberto
    Bosich, Daniele
    2018 IEEE INTERNATIONAL CONFERENCE ON ENVIRONMENT AND ELECTRICAL ENGINEERING AND 2018 IEEE INDUSTRIAL AND COMMERCIAL POWER SYSTEMS EUROPE (EEEIC / I&CPS EUROPE), 2018,
  • [49] Up-front payment under RD rule
    Chen H.-C.
    Review of Economic Design, 2004, 9 (1) : 1 - 10
  • [50] PREDICTION INTERVAL SEARCH SCHEME FOR THE MOVE-TO-THE-FRONT REPLACEMENT ALGORITHM
    NELSON, PR
    JOURNAL OF THE INSTITUTE OF MATHEMATICS AND ITS APPLICATIONS, 1979, 24 (02): : 231 - 236
12345