2006/01/02 by Eitan Bachmat, Bachmat, Eitan
Mathematics · #Advanced Combinatorial Mathematics #FOS: Mathematics #Optimization and Control (math.OC) #Probability (math.PR) #Random Matrices and Applications #Stochastic processes and statistical mechanics #math.OC #math.PR
paper · pdf · doi:10.48550/arxiv.math/0601025
19 pages
arxiv created 2006/01/02 · openalex publication_date 2006/01/02 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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