guillotine cuts versus general cuts

Question

Cutting problems are problems where a certain large object should be cut to several small objects. For example, imagine you have a factory that works with large sheets of raw glass, of width $W$ and length $L$. There are several buyers, each of which wants an unbounded number of small glass sheets. Buyer $i$ wants sheets of length $l_i$ and width $w_i$. Your goal is to cut small sheets from the large one, such that the total used is maximized and the waste is minimized (there are also other types of cutting and packing problems).

One common restriction in cutting problems is that the cuts must be guillotine cuts, i.e., each existing rectangle can be cut only to two smaller rectangles; it is impossible to make L-shapes etc. Obviously, the maximum used area with guillotine cuts might be smaller than the maximum used area without restriction.

My question is: Are there upper and lower bounds on the ratio between the optimal guillotine cut and the optimal general cut?

Related work: Song et al. (2009) describe an algorithm that uses a restricted type of guillotine cuts – twice-guillotine cuts. They prove, using geometric constraints, that the ratio between the maximum twice-guillotine cut to the maximum guillotine cut is bounded by $\frac{6}{7}$. I am looking for a comparable result about the ratio between the maximum guillotine cut to the maximum general cut.

Answer 1

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.

Let us start with the upper bound and assume we are given a square piece of glass with a side length of $2$. Furthermore, we have exactly one buyer who is interested in rectangular glass sheets of width $1-\varepsilon$ and length $1+\varepsilon$. Using general cuts, the optimal solution looks something like the following picture, with four of the desired rectangles placed around a little square of side length $\varepsilon$ in the middle.

It is easy to see that this cutting pattern can not be achieved via guillotine cuts. In fact, any cutting pattern using guillotine cuts can fit at most 3 of the desired rectangles into the original square. As a result, the worst ratio between guillotine cuts and general cuts is at least $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.