I need to prove that the modification of MTF, Move to front on every even request of an element, list update problem has a competitive ratio of 2.

How does one go about proving such results? (I'm aware of the amortized analysis but not sure how to apply in this case)

  • $\begingroup$ "need to prove" ? $\endgroup$ – Suresh Venkat Apr 26 '12 at 6:02
  • $\begingroup$ want to prove.. $\endgroup$ – Swair Apr 26 '12 at 6:08
  • 3
    $\begingroup$ This smells like homework. $\endgroup$ – Jeffε Apr 26 '12 at 6:21
  • $\begingroup$ Reading first chapter of the book Online Computation and Competitive analysis. Exercise 1.5 $\endgroup$ – Swair Apr 26 '12 at 6:22
  • $\begingroup$ Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the FAQ for more information. $\endgroup$ – Kaveh Apr 26 '12 at 6:33

This question is given as an exercise in the textbook by Borodin and El-Yaniv. Unfortunately, it is impossible to solve. Indeed, it was later discovered that MTF-every-other-access is not 2-competitive. See arxiv.org/abs/1311.7357 for a proof that the competitive ratio of the algorithm is in fact 2.5, and for a history of the false belief that the algorithm was 2-competitive.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.