Transposition is Nearly Optimal for IID List Update
Cet article confirme la conjecture de Rivest vieille de 50 ans en démontrant que la règle de transposition, une procédure sans mémoire, atteint un coût d'accès espéré dans la distribution stationnaire d'au plus OPT + 1 pour le problème de mise à jour de liste en modèle i.i.d.