which seem to precisely capture the increased difficulty in obtained good bounds for the multi-row case.

Motivated by this discussion we first consider LP’s whose columns $a^t$’s lie in *few* one-dimensional subspaces (Section \[sec:otp\]). For each of these subspaces, we are able to approximate the classifications induced in the columns lying in the subspace by considering a small subset of the induced classifications; patching together these partial classifications gives us a witness set for $\mathcal{X}$. However, this strategy as stated does not make use of the fact that the subspaces are embedded in an $m$-dimensional space, and hence leads to large witness sets. By establishing a connection between the “useful” patching possibilities with faces of a hyperplane arrangement in $\mathbb{R}^m$ (Lemma \[lemma:sizeP\]), we are able to make use of the dimension of the host space and exhibit witness sets of much smaller sizes, which leads to improved bounds.

For a general packing LP, we perturb the columns $a^t$’s to make them lie in few one-dimensional subspaces that form an ‘$\epsilon$-net’ of the space, while not altering the feasibility and optimality of the LP by more than a $(1 \pm \epsilon)$ factor (Section \[sec:rotp\]). Finally, we tighten the bound by using 