Min–max subsequence problems in multi-zone disk recording
✍ Scribed by Wil Michiels; Jan Korst
- Publisher
- Springer US
- Year
- 2001
- Tongue
- English
- Weight
- 188 KB
- Volume
- 4
- Category
- Article
- ISSN
- 1094-6136
- DOI
- 10.1002/jos.80
No coin nor oath required. For personal study only.
✦ Synopsis
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 ÿles. By alternately assigning the successive data blocks of a video ÿle to the di erent zones of a hard disk one can guarantee a higher transfer rate over a given period of time than otherwise can be guaranteed.
We brie y sketch the context of the ordering problem and indicate that it is NP-complete in the strong sense for each k¿3. For k = 2, we present an optimal algorithm. For k¿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 a ects the performance of the system. Copyright