, we show that the expected cost for every deterministic online algorithm is a ?(log n) factor more than the expected optimal cost [8]. Conceptually, underlying the lower bound construction is a complete binary tree T , of depth q = ?(log n), with n leaves. We think of each internal node of T as having a left and right subtree; thus the leaves of T can be associated with the positions on the track. We begin by choosing an uniformly random initial assignment ? of items to leaves. The adversary initially orders the items in the track to match this assignment, and will not move the items after this. The sequence of requests consists of q rounds. Each round i, 0 ? i ? q ? 1, 0. To obtain ? i , the depth-(q ? i) subtrees, We apply Yao's principle: For a particular input distribution

). and .. .. , Then v ?j (k) precedes v ? j (k ) in ? i if and only if j occurs before j in ?, or j = j and k occurs before k in ? j. We now bound the costs for the optimum. The only swap cost is incurred initially and is no more than n 2. During ? i , movement between two items in the same depth-(q ? i) subtree costs at most 2 i. Thus the total movement between items in the same depth-(q ? i) subtrees costs at most n2 i. Movement between two such items costs at most n. The movement cost for the first item is at most n. Also, movement between over i, Then, while maintaining the order of the subtrees, the 2 i leaves within each of the depth-(q ? i) subtrees are uniformly randomly ordered (again independent of all other random choices)

, We can generously assume that the online algorithm knows the adversary's strategy for constructing the sequences ? i and that it sees ? i just before round i. Before seeing ? i , the online player knows the depth-(q ? i + 1) subtrees of T , but it has no information at all on how depth

S. Albers, R. Bernhard-von-stengel, and . Werchner, A combined BIT and TIMESTAMP algorithm for the list update problem, Infor. Process. Lett, vol.56, issue.3, pp.135-139, 1995.

S. Albers and J. Westbrook, Self-organizing data structures, Online Algorithms, The State of the Art, pp.13-51, 1996.
DOI : 10.1007/bfb0029563

C. Ambühl, Offline list update is NP-hard, European Symposium on Algorithms (ESA), pp.42-51, 2000.

C. Ambühl, SIGACT news online algorithms column 31, SIGACT News, vol.48, issue.3, pp.68-82, 2017.

S. Arora, S. Rao, and U. V. Vazirani, Expander flows, geometric embeddings and graph partitioning, J. ACM, vol.56, issue.2, 2009.
DOI : 10.1145/1502793.1502794

URL : http://www.cs.princeton.edu/~arora/pubs/arvfull.pdf

O. Avissar, R. B. Rajeev, and D. Stewart, An optimal memory allocation scheme for scratch-pad-based embedded systems, ACM Trans. Embed. Comput. Syst, vol.1, issue.1, pp.6-26, 2002.

R. Banakar, S. Steinke, B. Lee, M. Balakrishnan, and P. Marwedel, Scratchpad memory: Design alternative for cache on-chip memory in embedded systems, Symposium on Hardware/Software Codesign, pp.73-78, 2002.

A. Borodin and R. El-yaniv, On randomization in online computation, IEEE Conference on Computational Complexity (CCC), pp.226-238, 1997.
DOI : 10.1109/ccc.1997.612318

U. Feige and J. R. Lee, An improved approximation ratio for the minimum linear arrangement problem, Inf. Process. Lett, vol.101, issue.1, pp.26-29, 2007.
DOI : 10.1016/j.ipl.2006.07.009

S. Gu, E. Sha, Q. Zhuge, Y. Chen, and J. Hu, Area and performance co-optimization for domain wall memory in application-specific embedded systems, Proceedings of the 52Nd Annual Design Automation Conference, Design Automation Conference, vol.20, pp.1-20, 2015.
DOI : 10.1145/2744769.2744800

D. Mark and . Hansen, Approximation algorithms for geometric embeddings in the plane with applications to parallel processing problems, IEEE Symposium on Foundations of Computer Science (FOCS), pp.604-609, 1989.

S. Kamali and A. López-ortiz, A survey of algorithms and models for list update. Space-Efficient Data Structures, Streams, and Algorithms, pp.251-266, 2013.

M. Kandemir, J. Ramanujam, and A. Choudhary, Exploiting shared scratch pad memory space in embedded multiprocessor systems, Design Automation Conference, pp.219-224, 2002.
DOI : 10.1109/dac.2002.1012623

M. Kandemir, J. Ramanujam, J. Irwin, N. Vijaykrishnan, I. Kadayif et al., Dynamic management of scratch-pad memory space, Proceedings of the 38th Annual Design Automation Conference, Design Automation Conference, pp.690-695, 2001.
DOI : 10.1109/dac.2001.935595

URL : http://jamaica.ee.pitt.edu/Archives/ProceedingArchives/Dac/Dac2001/papers/2001/dac01/pdffiles/42_1.PDF

S. Frank-thomson-leighton and . Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, J. ACM, vol.46, issue.6, pp.787-832, 1999.

N. D. Preeti-ranjan-panda, A. Dutt, and . Nicolau, Efficient utilization of scratch-pad memory in embedded processor applications, European Design and Test Conference, 1997.

S. Rao and A. W. Richa, New approximation techniques for some linear ordering problems, SIAM J. Comput, vol.34, issue.2, pp.388-404, 2004.
DOI : 10.1137/s0097539702413197

N. Reingold and J. Westbrook, Off-line algorithms for the list update problem, Inf. Process. Lett, vol.60, issue.2, pp.75-80, 1996.
DOI : 10.1016/s0020-0190(96)00144-5

URL : http://www.research.att.com/~jeffw/ps/list-update-opt.ps.gz

D. D. Sleator and R. E. Tarjan, Amortized efficiency of list update and paging rules, CACM, vol.28, issue.2, pp.202-208, 1985.
DOI : 10.1145/2786.2793

URL : http://www.win.tue.nl/~hermanh/onderwijs/2IL00/sleator-paging.pdf

B. Teia, A lower bound for randomized list update algorithms, Inf. Process. Lett, vol.47, pp.5-9, 1993.
DOI : 10.1016/0020-0190(93)90150-8

P. David, D. B. Williamson, and . Shmoys, The Design of Approximation Algorithms, 2011.