cięcia gilotynowe a cięcia ogólne

Problemy z cięciem to problemy, w których pewien duży obiekt powinien zostać pocięty na kilka małych obiektów. Na przykład, wyobraź sobie, że masz fabrykę, która współpracuje z dużymi arkuszami surowego szkła, o szerokości i długość L . Istnieje kilku nabywców, z których każdy chce nieograniczoną liczbę małych tafli szkła. Kupujący i chce arkusze o długości l I i szerokości w I . Twoim celem jest wycinanie małych arkuszy z dużego, tak aby całkowita wykorzystana ilość była zmaksymalizowana, a odpady zminimalizowane (istnieją również inne rodzaje problemów związanych z cięciem i pakowaniem ).$W$$L$$i$$l_i$$w_i$

Jednym z powszechnych ograniczeń w problemach cięcia jest to, że nacięcia muszą być cięciami gilotynowymi , tj. Każdy istniejący prostokąt można przyciąć tylko do dwóch mniejszych prostokątów; nie jest możliwe tworzenie kształtów litery L itp. Oczywiście, maksymalny wykorzystany obszar z cięciami gilotynowymi może być mniejszy niż maksymalny użyty obszar bez ograniczeń.

Moje pytanie brzmi: czy istnieją górne i dolne granice stosunku optymalnego cięcia gilotyny do optymalnego cięcia ogólnego?

Powiązana praca: Song et al. (2009) opisują algorytm wykorzystujący ograniczony typ cięć gilotynowych - dwa razy gilotyny . Udowadniają, stosując ograniczenia geometryczne, że stosunek między maksymalnym cięciem podwójnym gilotyną a maksymalnym cięciem gilotynowym jest ograniczony przez $\frac{6}{7}$

Although this is not tight, I can offer lower and upper bounds of $1/4$ and $3/4$ on the worst case ratio between guillotine cuts and general cuts.

Zacznijmy od górnej granicy i załóżmy, że otrzymujemy kwadratowy kawałek szkła o długości boku $2$. Ponadto mamy dokładnie jednego nabywcę, który jest zainteresowany prostokątnymi taflami szkła o szerokości$1-\varepsilon$ i długość $1+\varepsilon$. Korzystając z ogólnych cięć, optymalne rozwiązanie wygląda mniej więcej tak, jak na poniższym zdjęciu, z czterema pożądanymi prostokątami umieszczonymi wokół małego kwadratu o boku$\varepsilon$ pośrodku.

Łatwo zauważyć, że tego wzoru cięcia nie można osiągnąć za pomocą gilotyny. W rzeczywistości każdy wzór wycinania za pomocą nacięć gilotynowych może zmieścić maksymalnie 3 pożądane prostokąty w oryginalnym kwadracie. W rezultacie najgorszy stosunek między cięciami gilotynowymi a ogólnymi to przynajmniej$3/4$.

Next, we have a look at the lower bound. Let $W$ and $L$ be the side lengths of the original sheet of glass. Without loss of generality, we can assume that there exists a buyer $i$ such that $w_i \leq W$ and $l_i \leq L$. Otherwise, the original sheet would be unusable, no matter if we use guillotine cuts or general cuts. However, using guillotine cuts, we can always cut out at least one quarter of the original sheet by simply aligning the rectangles desired by buyer $i$, as shown in the following picture.

Notice that the red rectangle corresponds to one quarter of the whole sheet and is completely covered by the gray rectangles buyer $i$ desires. On the other hand, even if we use general cuts, we cannot use more than the whole sheet, which gives us a lower bound of $1/4$.

I am aware that the lower bound is quite weak and it can probably be improved with a bit more work. But it is a start.