Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-25T09:52:33.065Z Has data issue: false hasContentIssue false

Tail Bounds and Expectations for Random Arc Allocation and Applications

Published online by Cambridge University Press:  20 May 2003

PETER SANDERS
Affiliation:
Max-Planck-Institut für Informatik, Saarbrücken, Germany (e-mail: [email protected])
BERTHOLD VÖCKING
Affiliation:
Department of Computer Science, Universität Dortmund, Informatik 2, Baroper Str. 301, 44221 Dortmund, Germany (e-mail: [email protected])

Abstract

Suppose $n$ circular arcs of lengths $\len_i \in [0,1],0\leq i<n$, are placed uniformly at random on a unit length circle. We study the maximum overlap, i.e., the number of arcs that overlap at the same position of the circle. In particular, we give almost exact tail bounds for this random variable. By applying these tail bounds we can characterize the expected maximum overlap exactly up to constant factors in lower order terms. We illustrate the strength of our results by presenting new performance guarantees for three algorithmic applications: minimizing rotational delays for disks, scheduling accesses to parallel disks, and allocating memory blocks to limit cache interference misses.

Type
Research Article
Copyright
© 2003 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)