Average case analysis for batched disk scheduling and increasing subsequences

ABSTRACT

(MATH) We consider the problem of estimating the tour length and finding approximation algorithms for the asymmetric traveling salesman problem arising from the disk scheduling problem. Given N requests, we show that if the seek function has positive derivative at 0 the tour length is concentrated in probability around the value C_f,pN^1/2 for an explicit constant C_f,p dependent on the seek function and the distribution of requests. For linear seek function we provide even tighter bounds and provide an O(Nlog(N)) time algorithm for finding the optimal tour. The proof uses several results on the size and location of maximal increasing subsequences. To handle more general seek functions we introduce a more general concept of increasing subsequences. we provide order of magnitude estimates on the tour length for a wide class of seek functions with vanishing derivative at 0. For general seek functions we use some geometric information on the location of maximal generalized increasing subsequences obtained via Talagrand's isoperimetric inequalities to produce a probabilistic 1+&egr; approximation algorithm. These results complement the results on guaranteed approximation algorithms for this problem presented in [2].

REFERENCES

• 1: D. Aldous and P. Diaconis. Longest increasing subsequences: From patience sorting to the baik-deift-johansson theorem. Bull. of the AMS, 36(4):413--432, 1999.
• 2: M. Andrews , M. A. Bender , L. Zhang, New algorithms for the disk scheduling problem, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.550, October 14-16, 1996
• 3: E. Artin. The Gamma function. Holt, Reinhart and Wilson press, 1964.
• 4: J. Baik, P.A. Deift, and K. Johansson. On the distribution of the length of the length of the longest increasing subsequence of random permutations. Journal of the AMS, 12:1119--1178, 1999.
• 5: J.E. Beardwood, J.H. Halton, and J.M. Hammersley. The shortest path through many points. Proceedings of Cambridge philosophical society, 55:299--327, 1959.
• 6: E.G. Coffman, L.A. Klimko and B. Ryan. Analysis of scanning policies for reducing disk seek times. SIAM Journal of computing, 1(3), 1972.
• 7: J.D. Deuschel and O. Zeitouni. Limiting curves for iid records. Annals of probability, 23:852--878, 1995.
• 8: R.P. Dilworth. A decomposition theorem for partially ordered sets. Annals of (MATH)ematics, 51:161--166, 1950.
• 9: G. Gallo, F. Malucelli and M. Marre. Hamiltonian paths algorithms for disk scheduling. em Universita of Pisa technical report, 20/94, 1994.
• 10: C. C. Gotlieb , G. H. MacEwen, Performance of Movable-Head Disk Storage Devices, Journal of the ACM (JACM), v.20 n.4, p.604-623, Oct. 1973 [doi>10.1145/321784.321789]
• 11: John Linwood Griffin , Steven W. Schlosser , Gregory R. Ganger , David F. Nagle, Modeling and performance of MEMS-based storage devices, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.56-65, June 18-21, 2000, Santa Clara, California, United States
• 12: J.M. Hammersley. A few seedlings of reserach. Proceedings of the sixth Berkley symposium on (MATH)ematical statistics and probability, 1, 1972.
• 13: Micha Hofri, Disk scheduling: FCFS vs.SSTF revisited, Communications of the ACM, v.23 n.11, p.645-653, Nov. 1980 [doi>10.1145/359024.359034]
• 14: D. Jacobson and J. Wilkes. Disk scheduling algorithms based on rotational position. HP labs technical report, HPL-CSP-91-7rev1, 1991.
• 15: R.M. Karp. Probabilistic analysis of partitioning algorithms for the traveling salesman problem in the plane. (MATH)ematical operations research, 2:209--224, 1977.
• 16: B.F. Logan and L.A. Shepp. A variational problem for random young tableaux. Advances in (MATH)ematics, 26:206--222, 1977.
• 17: P. Sanders and B. Vocking. Random arc allocations and applications to disks, drums and drams. Preprint, June 2001.
• 18: M. Seltzer, Chen P. and J. Ousterhout. Disk scheduling revisited. Proceedings of the Usenix technical conference, 313--324, winter 1990.
• 19: M. Talagrand. Concentration of measure and isoperimetric inequalities in product spaces. Pub. (MATH). I.H.E.S, 81:73--203, 1995.
• 20: A.M. Vershik and S.V. Kerov. Asymptotics of the plancherel measure of the symmetric group and the limiting form of young tables. Soviet (MATH). Dokl., 18:527--531, 1977.
• 21: J.E. Yukich. Probability theory of classical Euclidean optimization problems. Lecture notes in (MATH)ematics 1675, Springer verlag, 1998.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Numerical algorithms

General Terms:
Algorithms, Experimentation, Performance, Theory