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

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

2006-01-02

arxiv.org/abs/math/0601025v1

Mathematics

Optimization and Control

19 pages

Scientific paper

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. The optimal disk scheduling algorithm of Andrews, Bender and Zhang is interpreted as a simple peeling process on points in a 2 dimensional space-time w.r.t the causal structure. The patience sorting algorithm for finding the longest increasing subsequence in a permutation can be given a similar interpretation. Using this interpretation we show that the optimal tour length is the length of the maximal curve with respect to a Lorentzian metric on the surface of the disk drive. This length can be computed explicitly in some interesting cases. When the probability distribution is assumed uniform we provide finer asymptotics for the tour length. The interpretation also provides a better understanding of patience sorting and allows us to extend a result of Aldous and Diaconis on pile sizes

Affiliated with

Also associated with

No associations

Rating

Analysis of disk scheduling, increasing subsequences and space-time geometry does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Analysis of disk scheduling, increasing subsequences and space-time geometry, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Analysis of disk scheduling, increasing subsequences and space-time geometry will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-41569