the idea of periodically recomputing the classification, following [@agrawal] (Section \[sec:rdpa\]).

OTP for almost 1-dim columns {#sec:otp}
============================

In this section we describe and analyze the algorithm [<span style="font-variant:small-caps;">OTP</span>]{}(One-Time Pricing) over LP’s whose columns are contained in few 1-dimensional subspaces of $\mathbb{R}^{m}$. The overall goal is to find an appropriate dual (perhaps infeasible) solution $p$ for and use it to classify the columns of the LP. More precisely, given $p \in \mathbb{R}^m$, we define $x(p)_t = 1$ if $\pi_t > p a^t$ and $x(p)_t = 0$ otherwise. Thus, $x(p)$ is the result of classifying the columns $(\pi_t, a^t)$’s with the homogeneous hyperplane in $\mathbb{R}^{m+1}$ with normal $(-1, p)$. The motivation behind this classification is that it selects the columns which have positive reduced cost with respect to the dual solution $p$, or alternatively, it solves to optimality the Lagrangian relaxation using $p$ as multipliers.

[*Sampling LP’s.*]{} In order to obtain a good dual solution $p$ we use the (random) LP consisting on the first $s$ columns of with appropriately scaled right-hand side.

$$\begin{aligned}
 \tag{$(s, \delta)$-LP} \label{eq:sdLP}
            \max & \sum_{t = 1}^{s} \pi_{\sigma(t)} x_{\sigma(t)} \\
            &\sum_{t = 1}^{s} a^{\sigma(t)} x_{\sigma(t)} \le \frac{s}{n} \delta B \notag \\
            &x_{\sigma(t)} \in [0,1] \ \ 