Back to Search
Start Over
Packing Random Intervals On-Line
- Source :
- Algorithmica; 19981201, Vol. 22 Issue: 4 p448-476, 29p
- Publication Year :
- 1998
-
Abstract
- Abstract.: Starting at time 0, unit-length intervals arrive and are placed on the positive real line by a unit-intensity Poisson process in two dimensions; the probability of an interval arriving in the time interval [t,t+ t] with its left endpoint in [y,y+ y] is t y + o( t y ). Fix x 0. An arriving interval is accepted if and only if it is contained in [0,x] and overlaps no interval already accepted. We study the number N <subscript> x </subscript> (t) of intervals accepted during [0,t] . By Laplace-transform methods, we derive large-x estimates of EN <subscript> x </subscript> (t) and VarN <subscript> x </subscript> (t) with error terms exponentially small in x uniformly in t (0,T) , where T is any fixed positive constant. We prove that, as , EN <subscript> x </subscript> (t) , VarN <subscript> x </subscript> (t) , uniformly in t (0,T) , where and are given by explicit, albeit complicated formulas. Using these asymptotic estimates we show that N <subscript> x </subscript> (t) satisfies a central limit theorem, i.e., for any fixed t where (0,1) is a standard normal random variable, and denotes convergence in distribution. This stochastic, on-line interval packing problem generalizes the classical parking problem, the latter corresponding only to the absorbing states of the interval packing process, where successive packed intervals are separated by gaps less than 1 in length. We verify that, as , (t) and (t) converge to <subscript>*</subscript> = 0.748 . . . and <subscript>*</subscript> = 0.03815 . . ., the constants of Rényi and Mackenzie for the parking problem. Thus, by comparison with the parking analysis in a single space variable, ours is a transient analysis involving both a time and a space variable. Our interval packing problem has applications similar to those of the parking problem in the physical sciences, but the primary source of our interest is the modeling of reservation systems, especially those designed for multimedia communication systems to handle high-bandwidth, real-time demands.
Details
- Language :
- English
- ISSN :
- 01784617 and 14320541
- Volume :
- 22
- Issue :
- 4
- Database :
- Supplemental Index
- Journal :
- Algorithmica
- Publication Type :
- Periodical
- Accession number :
- ejs12556540
- Full Text :
- https://doi.org/10.1007/PL00009233