Min-max subsequence problems in multi-zone disk recording

We study the problem of ordering a collection of n numbers such that the maximum sum of k successive numbers is minimized. The problem occurs in the design of video servers and in-home hard disk recorders used for storage of video files. By alternately assigning the successive data blocks of a video file to the different zones of a hard disk one can guarantee a higher transfer rate over a given period of time than otherwise can be guaranteed. We briefly sketch the context of the ordering problem and indicate that it is NP-complete in the strong sense for each k greater than or equal to 3. For k = 2, we present an optimal algorithm. For k greater than or equal to 3, we present an approximation algorithm for which we give performance bounds. Furthermore, we show by an example how the resulting assignment of data blocks to the zones affects the performance of the system. Copyright (C) 2001 John Wiley & Sons, Ltd.