The two-dimensional knapsack problem asks: given a square container and a set of rectangles with profits, which subset fits and maximizes total value? The problem is hard, and the best polynomial-time algorithms achieve approximation ratios around 1.5. A natural extension allows rotating rectangles by 90 degrees before packing. Adding this freedom seems like it should make the problem harder — more choices, more configurations to consider.
Kar, Khan, and Wiese (arXiv:2603.23970) show the opposite for the cardinality case (all items equally valuable). With rotations, they construct a polynomial-time approximation scheme (PTAS) — an algorithm that gets arbitrarily close to optimal. Without rotations, no PTAS is known. The added degree of freedom doesn't increase difficulty; it unlocks a structural property that simplifies approximation.
Note (2026-11-12; read against the paper's full text): the paper does not show that rotations make the problem easier. It says that a PTAS for the problem with rotations was an open question even in the cardinality case, presents one for that case, and shows that near-optimal solutions with all items packed in a constant number of containers exist with rotations, in contrast to the setting without rotations; it also improves the best known ratio for the weighted case without rotations to 13/7 plus epsilon, and proves a running-time lower bound of n to the power of omega of 1/epsilon for any approximation scheme with or without rotations, even in the cardinality case, assuming the k-SUM conjecture. So no separation between the two problems is established, and the essay's framing that the extra freedom unlocks a simpler structure and that rotation is a source of regularity is its interpretation of the container result.
The key insight is a new resource contraction lemma: with rotations, near-optimal solutions exist where all items are packed greedily inside a constant number of rectangular containers. This container-based structure doesn't hold without rotations, because fixed orientations create awkward gaps that resist simple packing. Rotation eliminates the worst-case geometric configurations that force complex arrangements.
But the story has a boundary. For the weighted case (items have different values), they prove that the container-based approach cannot beat 1.5 — yet still manage to break through with a 1.497-approximation using additional techniques. The structural barrier is real but circumventable.
The result illustrates a counterintuitive principle in optimization: constraints that seem to restrict the problem can actually make it harder by preventing helpful structural simplifications. Removing a constraint (fixed orientation) exposes a cleaner mathematical structure (constant containers) that enables better algorithms. The degree of freedom isn't just another axis of complexity — it's a source of regularity.