Name
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
x
(t) of intervals accepted during [0,t] . By Laplace-transform methods, we derive large-x estimates of EN
x
(t) and VarN
x
(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
x
(t)
, VarN
x
(t)
, uniformly in t
(0,T) , where and are given by explicit, albeit complicated formulas. Using these asymptotic estimates we show that N
x
(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
* = 0.748 . . . and
* = 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. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1007/PL00009233 | Algorithmica |
Keywords | Field | DocType |
Key words. Interval packing,Parking problem,Reservation systems,Asymptotic probabilistic analysis,On-line packing. | Discrete mathematics,Combinatorics,Random variable,Real line,Poisson process,Mathematics | Journal |
Volume | Issue | ISSN |
22 | 4 | 0178-4617 |
Citations | PageRank | References |
2 | 0.79 | 2 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| e g coffman | 1 | 1158 | 379.75 |
| Leopold Flatto | 2 | 32 | 7.69 |
| Predrag R. Jelenkovic | 3 | 219 | 29.99 |
| Bjorn Poonen | 4 | 77 | 16.89 |