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.
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.