Hostname: page-component-74656f9884-rdgjk Total loading time: 0 Render date: 2026-11-08T00:00:33.682Z 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: sanders@mpi-sb.mpg.de)
BERTHOLD VÖCKING
Affiliation:
Department of Computer Science, Universität Dortmund, Informatik 2, Baroper Str. 301, 44221 Dortmund, Germany (e-mail: voecking@ls2.cs.uni-dortmund.de)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Copyright
© 2003 Cambridge University Press