-1
$\begingroup$

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)

Improve this question
$\endgroup$
6
  • $\begingroup$ "need to prove" ? $\endgroup$
    – Suresh Venkat
    Apr 26, 2012 at 6:02
  • $\begingroup$ want to prove.. $\endgroup$
    – Swair
    Apr 26, 2012 at 6:08
  • 3
    $\begingroup$ This smells like homework. $\endgroup$
    – Jeffε
    Apr 26, 2012 at 6:21
  • $\begingroup$ Reading first chapter of the book Online Computation and Competitive analysis. Exercise 1.5 $\endgroup$
    – Swair
    Apr 26, 2012 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, 2012 at 6:33

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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