Probabilistic analysis for stochastic Rectangle Packing Problem algorithm

In this paper we consider a modified Rectangle Packing Problem where for each rectangle (module) its width and height come from uniform probability distribution between 0 and 1 - U(0,1). We provide a probabilistic analysis of a simple polynomial-time algorithm for Rectangle Packing Problem. At the end a comparison to the computer simulations is presented.

---

W tej pracy rozważamy Problem Pakowania Bloków, który występuje w wielu gałęziach przemysłu, np. w projektowaniu układów scalonych, cięciu bloków kamiennych, przemyśle tekstylnym. Rozważamy zmodyfikowany problem, w którym wysokości i szerokości bloków są zadane jednostajnym, ciągłym rozkładem prawdopodobieństwa U(0,1). W tej pracy prezentujemy analizę probabilistyczną skuteczności algorytmu Prezentujemy również wyniki symulacji komputerowych i porównujmy je z wynikami teoretycznymi