we have $a^t = \|a^t\|_{\infty} c^j$. An important observation is that now we can order the columns (locally) by the ratio of profit over budget occupation: without loss of generality assume that for all $j \in [K]$ and $t, t' \in C_j$ with $t < t'$, we have $\frac{\pi_t}{\|a^t\|_{\infty}} \ge \frac{\pi_{t'}}{\|a^{t'}\|}_{\infty}$.[^3]

Given a classification $x$, we use $x|_{C_j}$ to denote its projection onto the coordinates in $C_j$; so $x|_{C_j}$ is the induced classification on columns with indices in $C_j$. Similarly, we define $\mathcal{X}|_{C_j} = \{x|_{C_j} : x \in \mathcal{X}\}$ as the set of all classifications induced in the columns in $C_j$. The most important structure that we get from working with 1-d subspaces, which is implied by the local order of the columns, is the following.

\[lemma:chain\] For each $j \in [K]$, the sets in $\mathcal{X}|_{C_j}$ are prefixes of $C_j$.

To simplify the notation fix $i \in [m]$ for the rest of this section, so we aim at providing witness sets for $\mathcal{X}_i^+$ and $\mathcal{X}_i^-$. The idea is to group the classifications according to their budget occupation caused by the different column classes $C_j$’s. To make this formal, start by covering the interval $[0, B + m]$ with intervals $\{I_\ell\}_{\ell 