Pakowanie online prostokątów i d-wymiarowych kostek

Abstract

Przedmiotem tej rozprawy jest pakowanie online d-wymiarowych boxów oraz d-wymiarowych kostek. Oznaczmy przez b(d) [przez c(d), odpowiednio] największą liczbę taką, że dowolny ciąg d-wymiarowych boxów [kostek, odpowiednio] o krawędziach długości co najwyżej 1 i całkowitej objętości nie większej niż b(d) [niż c(d), odpowiednio] można upakować w d-wymiarowej kostce jednostkowej (tzn. kostce o krawędziach długości 1). W rozdziale 2 prezentuję algorytm pakowania online prostokątów. Stosując ten algorytm pokazuję, że b(2) jest większe lub równe 0,2837. Ponadto w rozdziale 3 dowodzę, że b(d) jest nie mniejsze niż (3-2√2)·3-d dla d większego niż 2. W rozdziale 4 wykazuję, że jeżeli n jest nie mniejsze niż 3 oraz d jest równe 3 lub 4 albo jeżeli n jest liczbą naturalną dodatnią oraz d większe niż 4, to dowolny ciąg d-wymiarowych kostek o krawędziach długości nie większej niż 1 i o całkowitej objętości co najwyżej (n+1) ·2-d można upakować online w n jednostkowych d-wymiarowych kostkach. W rozdziale 5 pokazuję, że powyższy wynik jest słuszny również dla n = 1 i d = 4, to znaczy, że c(4) jest większe lub równe 1/8. Jest to najważniejsza część niniejszej rozprawy. W rozdziale 6 podaję wyniki (bez dowodów) dotyczące zagadnienia pakowania do binów.

In this dissertation I examine the online packing of d-dimensional boxes and d-dimensional cubes. Denote by b(d) [by c(d), respectively] the greatest number such that any sequence of d-dimensional boxes [cubes, respectively] of edge length smaller than or equal to 1 and of total volume not greater than b(d) [than c(d), respectively] can be packed online into the d-dimensional unit cube (i.e., a cube of edges of length 1). In Chapter 2, I describe an algorithm for online packing of rectangles. By using this algorithm I show that b(2) is greater than or equal to 0.2837. Moreover, in Chapter 3 I prove that b(d) is not smaller than (3-2√2)·3-d for d greater than 2. In Chapter 4 I show that if n is integer not smaller than 3 and d equals 3 or 4, or if n is positive integer and d is greater than 4, then any sequence of d-dimensional cubes of edge lengths not greater than 1 whose total volume does not exceed (n+1) ·2-d can be online packed into n unit d-dimensional cubes. In Chapter 5 I show that this result holds true also for n = 1 and d = 4, i.e., c(4) is greater than or equal to 1/8. This is the crucial result in the dissertation. In chapter 6 I give results (without proofs) regarding the bin packing problem.