Prof. Eitan Bachmat

We consider the problem of estimating the average tour length of the asymmetric TSP arising from the disk scheduling problem with a linear seek function and a probability distribution on the location of I/O requests. We provide a law of large numbers expression, for the expected tour size and compute it explicitely in the most interesting cases. We also provide finer asymptotic estimates in the case of a uniform request distribution. Our methods relate disk scheduling to the problem of finding the longest increasing subsequence in a permutation. Our tour length estimates also answer questions on the asymptotics of the connect-the dots problem with Lipschitz functions which was raised in Adv. Appl. Probab. 37, 571-603 (2005). In the last section we show that all the above problems can be interpreted naturally, in terms of Lorentzian geometry. We generalize the main results to this setting.