Search

In this paper, we consider algorithms to pack rectangles into a strip. As the main result we present an algorithm that packs rectangles online and for which the ratio of expected wasted area to expected occupied area tends to zero as the number of rectangles increases. The research was supported by the Russian Foundation for Basic Research, grants 05–01–00798 and 04–01–00359. [ABSTRACT FROM AUTHOR]

The distribution of jobs in a system with m identical parallel processors which minimises the load of the maximally loaded processor is an NP-hard problem. Many approximate algorithms are developed for this problem, but for the version of the problem where the jobs arrive ad must be treated on-line there is no algorithm possessing the guaranteed estimate which is less than 1 + 1 / ... for m ≥ 4 and tends to 1.837 as m → ∞. In this paper, we consider the version of the problem where jobs arrive one by one and must be treated on-line under the additional condition that the total duration of the jobs is known. For this version of the problem we suggest an algorithm with the guaranteed estimate equal to 5/3. [ABSTRACT FROM AUTHOR]

We consider a problem to pack rectangles into several semi-infinite strips of certain widths. We suggest two simply realised online algorithms, that is, algorithms which pack rectangles just at the moments of their arrivals. It is shown that the accuracy of the former algorithm cannot be approximated by any absolute constant. The latter algorithm guarantees a constant multiplicative accuracy, and the obtained estimate of the multiplicative accuracy is unimprovable. The research was supported by the Russian Foundation for Basic Research, grant 05–01–00798. [ABSTRACT FROM AUTHOR]

We study the question on average and typical values of sums of pairwise Hamming distances for subsets of vertices of the n-dimensional unit cube. We suggest an approach to the problem of evaluation of average and typical values of arbitrary functionals defined on subsets of a finite set as the sum of values assigned to ordered pairs of elements of this set; general formulas for this case are obtained. We find average and typical values of sums of pairwise distances in the case of all subsets of vertices of the n-dimensional unit cube and of sums of pairwise distances for subsets of vertices of fixed cardinality. This research was supported by the Russian Foundation for Basic Research, grant 01–01–00266. [ABSTRACT FROM AUTHOR]