2026-10-02T03:54:54Zhttps://repozytorium.amu.edu.pl/server/oai/requestoai:repozytorium.amu.edu.pl:10593/256972026-07-09T09:55:21Zcom_10593_8com_10593_51col_10593_769col_10593_104
AMUR - Repozytorium Uniwersytetu im. Adama Mickiewicza w Poznaniu
advisor
Januszewski, Janusz. Promotor
author
Zielonka, Łukasz
2020-07-13T08:14:06Z
2020-07-13T08:14:06Z
2020
http://hdl.handle.net/10593/25697
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.
pl
info:eu-repo/semantics/restrictedAccess
pakowanie online
online packing
prostokąty
rectangles
boxy
boxes
kostki
cubes
Pakowanie online prostokątów i d-wymiarowych kostek
doctoral thesis
URL
https://repozytorium.amu.edu.pl/bitstreams/dde3b5ee-450c-4281-87d3-a53e06b69af6/download
File
MD5
be2d0acd3abeedc28765a8cf6a26bafd
515288
application/pdf
LZielonka_rozprawa.pdf
URL
https://repozytorium.amu.edu.pl/bitstreams/8b7076b6-86e1-4857-a63b-dfc4053a1b35/download
File
MD5
32448efd61c7c8d0f130183c35e571e6
106115
text/plain
LZielonka_rozprawa.pdf.txt