Faculty Digital Archive

Archive@NYU >
Stern School of Business >
IOMS: Information Systems Working Papers >

Please use this identifier to cite or link to this item: http://hdl.handle.net/2451/14184

Title: The Two Headed Disk: Stochastic Dominance of the Greedy Policy
Authors: Seshadri, Sridhar
Rotem, Doron
Keywords: Two headed disk
Seek time
Stochastic optimality
Analysis of algorithms
Issue Date: 1995
Publisher: Stern School of Business, New York University
Series/Report no.: IS-97-26
Abstract: In his paper "Should the two-headed disk be greedy? - Yes, it should" Hofri defined a "greedy policy" as follows. Assuming that the range of disk addresses is [0,1], a request at location x is served by the closest arm while the other arm jockeys to a new position, z, where z = (1/3)x or z = 2/3 +x/3 depending on whether x is larger or smaller than 1/2. Hofri proved that this policy minimizes the expected seek distance for uniform request probabilities and conjectured that it stochastically dominates every other policy. Stochastic dominance is of practical importance in this context as it guarantees that a policy that optimizes expected seek distance also guarantees optimal seek time. The main result of this paper is a proof of Hofri's conjecture. The paper contains two proofs, the first establishes the conjecture, and the second shows that if the seek distance is stochastically minimized under a repositioning policy, then the policy must be Hofri's greedy policy and the request distribution must be uniform.
URI: http://hdl.handle.net/2451/14184
Appears in Collections:IOMS: Information Systems Working Papers

Files in This Item:

File Description SizeFormat
IS-97-26.pdf1.16 MBAdobe PDFView/Open

Items in Faculty Digital Archive are protected by copyright, with all rights reserved, unless otherwise indicated.

 

The contents of the FDA may be subject to copyright, be offered under a Creative Commons license, or be in the public domain.
Please check items for rights statements. For information about NYU’s copyright policy, see http://www.nyu.edu/footer/copyright-and-fair-use.html 
Valid XHTML 1.0 | CSS