A packing of a collection of rectangles is a disjoint subcollection. In a recent paper, Coffman et al. (1999) prove that the cardinality of a maximum packing of a family of n random rectangles in 0, ...1 2 is of order n 1/2 . We obtain tight bounds on the same quantity when the random rectangles are of a specified volume.
A packing of a collection of rectangles contained in 0, 12is a disjoint subcollection; the wasted space is the measure of the area of the part of 0, 12not covered by the subcollection. A simple ...packing has the further restriction that each vertical line meets at most one rectangle of the packing. Given a collection of N independent uniformly distributed subrectangles of 0, 1, we proved in a previous work that there exists a number K such that the wasted space WNin an optimal simple packing of these rectangles satisfies for all N$EW_N \leq \frac{K}{\sqrt{N}} \exp K \sqrt{\log N}.$We prove here that$\frac{1}{K\sqrt{N}} \exp \frac{1}{K}\sqrt{\log N} \leq EW_N.$
It is known that given
N random subintervals of 0, 1, one can find a disjoint subcollection that covers all of 0, 1 except a set of length about
(
log N)
2
N
. We investigate what happens when the ...distribution of the intervals is biased to favor shorter intervals or intervals close to the endpoints of 0, 1. Quite surprizingly, the order
(
log N)
2
N
is very robust.
In this problem, we are given N uniformly distributed random intervals of 0, 1. For each random interval, I , we are given a weight X I . These weights are independent, independent of the intervals, ...and satisfy P ( X I t ) = t , where > 0. A packing of the family is a disjoint set of these intervals. Its cost is C = | R | + I X I | I |, where R is the part of 0, 1 that is not covered by . We are interested in the optimal (=minimal) cost W N among all packings of the random family. We consider the case 1 < < 2. If we define by ( /2) = , we show that for some constant K depending on only, we have
Consider n random intervals I
1, …, I
N
chosen by selecting endpoints independently from the uniform distribution. A packing of I
1, …, I
N
is a disjoint sub-collection of these intervals: its wasted ...space is the measure of the set of points not covered by the packing. We investigate the random variable W
N
equal to the smallest wasted space among all packings. Coffman, Poonen and Winkler proved that EW
N
is of order (log N)2/N. We provide a sharp estimate of log P(W
N
≥ t (log N)2 / N) and log P(W
N
≤ t (log N)2 / N) for all values of t.
Packing rectangles and intervals Rhee, Wansoo T.
International journal of computer mathematics,
2001, Letnik:
76, Številka:
4
Journal Article
Recenzirano
Consider a parameter α>0, and a large integer AT. Assume that for P≥1, we are given a family I
p
of 2
-αp
N random intervals of 0,1, and consider the union I of the families I
p
. A packing of I is a ...disjoint sub family of I. The cost of the packing is the sum of the wasted space (the measure of the part of 0,1 not covered by the packing) and the costs of the intervals of the packing, where, if l∈ I
p
, the cost of I is 2
-p
|I|. We estimate as a function of N, the expected value of the cost of an optimal packing. We discover the very surprising fact that (up to terms of smaller order) this cost behaves as N
-1/2
for all 1≤α≤2. This problem is motivated by a problem of packing random rectangles.
We give a unified simple proof of recent results of Alexander concerning the rate of convergence of the mean length of the longest common subsequence of two random sequences and the rate of ...convergence of the expected value of certain passage times in percolation theory.
Packing Random Intervals Rhee, WanSoo T.; Talagrand, Michel
The Annals of applied probability,
05/1996, Letnik:
6, Številka:
2
Journal Article
Recenzirano
Odprti dostop
A packing of a collection of subintervals of 0, 1 is a pairwise disjoint subcollection of the intervals; its wasted space is the measure of the set of points not covered by the packing. Consider n ...random intervals, I1, ..., In, chosen by selecting endpoints independently from the uniform distribution. We strengthen and simplify the results of Coffman, Poonen and Winkler, and we show that, for some universal constant K and for each t ≥ 1, with probability greater than or equal to 1 - 1/nt, there is a packing with wasted space less than or equal to Kt(log n)2/n.
A fleet of vehicles located at a common depot must serve customers located throughout the plane. Without loss of generality, the depot will be located at the origin. Each vehicle must start at the ...depot, travel in turn to each customer its serves and go back to the depot. Each vehicle can serve at most k customers. The objective is to minimize the total distance traveled by the fleet. In our model, the customers X1, ..., Xnare independent and uniformly distributed over the unit disc. If R'(X1, ..., Xn) denotes the optimal solution with these customer locations, we show that with overwhelming probability we have$\big|R'(X_1, \ldots, X_n) - \frac{2}{k} \sum_{i \leq n} \|X_i\| - \xi \sqrt{n} big| \leq K(n \log n)^{1/3},$where ξ and K are constants that depend on k only.
A classical paper by Steele establishes a limit theorem for a wide class of random processes that arise in problems of geometric probability. We propose a different (and arguably more general) set of ...conditions under which complete convergence holds. As an application of our framework, we prove complete convergence of$M(X_1, \ldots, X_n)/\sqrt n$, where M(X1, ..., Xn) denotes the shortest sum of the lengths of$\lfloor n/2\rfloor$segments that match$\lfloor n/2\rfloor$disjoint pairs of points among X1, ..., Xn, where the random variables X1, ..., Xn, ... are independent and uniformly distributed in the unit square.
PDF
