Abstract:

Modern disk drives can rearrange the order in which they
service requests so that the total time needed to service all the
requests is minimized. Given any two disk locations the physical
characteristics of the disk and in particular the seek function
determine how much time is needed to move from the first location to
the other. Given N requests to the disk the problem then is to
find a minimal Hamiltonian cycle on the graph whose vertices 
correspond to the requests and whose directed edges are weighted by 
access times between the requests. 
Another interesting question is to find the average length
of the optimal cycle. In 1996 Andrews, Bender and Zhang showed that in 
general the problem is NP-Complete, gave a 3/2 approximation algorithm 
for the general case and showed that the case of a linear seek 
function is polynomial. 
We use a result of Deuschel and Zeitouni on the increasing subsequence
problem to show that in the linear seek function case, 
in probability the length of the  optimal tour is $C\sqrt(N)$ for
an explicit constant C which depends on the characteristics of the
disk and the distribution of the requests. We also present a
conjecture which will allow us to generalize the results to
a large class of seek functions.

In the talk we will survey the results of Andrews, bender and Zhang,
survey some results of Hammersley, Kerov-Vershik,Logan-Shepp, Deuschel-
Zeitouni and Deift,Baik and Johansson on the increasing subsequence
problem and finally explain how these results are intimately connected
to our problem.