2-конкурентоспособность MTF

Question

Я знаю, как MTF является 2-конкурентным, если предположить, что оптимальному алгоритму OPT разрешено:

1. доступ к k-му элементу в списке по цене k,
2. решите бесплатно переместить этот k-й элемент в любое место ближе к началу списка,
3. поменяйте местами соседние элементы в списке на стоимость 1.

Доказательство стандартное и встречается повсеместно в сети. Однако как меняется доказательство, когда 3-я операция не разрешена? В частности, ни для MTF, ни для OPT не разрешены платные свопы: разрешены только операции 1 и 2 для OPT и 1 и свободное перемещение вперед для MTF.

Answer 1

Доказательство не меняется - алгоритм не подвержен влиянию, а противник слабее. MTF все еще только 2-конкурентен в ограниченном режиме, поскольку существует семейство последовательностей доступа с соотношением 2 - o (1), где OPT вообще не перемещает элементы.