ALCOMFT-TR-02-31

Peter Sanders and Berthold Vöcking
Random Arc Allocation and Applications
MPI. Work packages 1 and 4. May 2002.

Abstract: The paper considers a generalization of the well known random placement of balls into bins. Given n circular arcs of lengths <=n₁,\ldots,<=n_n we study the maximum number of overlapping arcs on a circle if the starting points of the arcs are chosen randomly. We give almost exact tail bounds on the maximum overlap of the arcs. These tail bounds yield a characterization of the expected maximum overlap that is tight up to constant factors in the lower order terms. We illustrate the strength of our results by presenting new performance guarantees for several application: Minimizing rotational delays of disks, scheduling accesses to parallel disks and allocating memory to limit cache interference misses.

Postscript file: ALCOMFT-TR-02-31.ps.gz (88 kb).