$x^S$ is a feasible solution for with value at least $(1 - 3\epsilon) {\ensuremath{\textrm{OPT}}}$.

Connection to PAC learning
--------------------------

We assume from now on that $B \ge \Omega(\frac{m}{\epsilon^3} \log \frac{K}{\epsilon})$. Let $\mathcal{X} = \{x(p) : p \in \mathbb{R}^m_+\} \subseteq \{0,1\}^n$ denote the set of all possible linear classifications of the LP columns which can be generated by [<span style="font-variant:small-caps;">OTP</span>]{}. With slight overload in the notation, we identify a vector $x \in \{0,1\}^n$ with the subset of $[n]$ corresponding to its support.

Given a scenario, we say that $x^S$ is *bad* if it does not satisfy the properties of Lemma \[lemma:goodOtp\], namely $x^S$ is either infeasible or has value less than $(1 - 3\epsilon) {\ensuremath{\textrm{OPT}}}$. We say that $x^S$ is *good* otherwise.

As noted in previous work, since our decisions are made based on reduced costs it suffices to analyze the *budget occupation* (or complementary slackness) of the solution in order to understand its *value*. To make this precise, given $x \in \{0,1\}^n$ let $a_i(x) = \sum_{t \in x} a_i^t$ be its occupation of the $i$th budget and let $a^S_i(x) = \frac{1}{\epsilon}\sum_{t \in x \cap S} a_i^t$ be its appropriately scaled occupation of $i$th budget in the sampled LP (recall $|S| 