<p>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.</p>

CC BY-SA 3.0
2016-06-22T09:33:19.353Z
2016-06-22T09:33:19.353Z
JWM
<p>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.</p>

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

CC BY-SA 3.0
2012-04-26T06:02:59.010Z
"need to prove" ?
Suresh Venkat
CC BY-SA 3.0
2012-04-26T06:08:52.403Z
want to prove..
Swair
CC BY-SA 3.0
2012-04-26T06:21:43.807Z
This smells like homework.
Jeffε
CC BY-SA 3.0
2012-04-26T06:22:49.233Z
Reading first chapter of the book Online Computation and Competitive analysis. Exercise 1.5
Swair
CC BY-SA 3.0
2012-04-26T06:33:40.750Z
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.
Kaveh
CC BY-SA 3.0
2012-04-26T06:34:00.860Z
For non-research questions please consider posting on [cs.se].
Kaveh
<ds.algorithms><online-algorithms>
Competitive ratio of Move To Front in alternate access - List Update Problem
Swair
# Competitive ratio of Move To Front in alternate access - List Update Problem

(Asked by: username_0 on 2012-04-26)

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)

**Tags:** ds.algorithms, online-algorithms

> **Comments:**
> **username_1**: "need to prove" ?  
> **username_0**: want to prove..  
> **username_2**: This smells like homework.  
> **username_0**: Reading first chapter of the book Online Computation and Competitive analysis. Exercise 1.5  
> **username_3**: 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.  
> **username_3**: For non-research questions please consider posting on [cs.se].  

---

## 1 answers

### Answer by username_4 on 2016-06-22. Score: 1

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.


---

