Analysis of disk scheduling, increasing subsequences and space-time geometry

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 distribut…