\ \ t = 1, \ldots, s \notag .
        \end{aligned}$$

$$\begin{aligned}
 \tag{$(s, \delta)$-Dual} \label{eq:sdDual}
            \min \ & \frac{s}{n} \delta B \sum_{i = 1}^{m} p_i + \sum_{t = 1}^s \alpha_{\sigma(t)} \\
            & p a^{\sigma(t)} + \alpha_{\sigma(t)} \ge \pi_{\sigma(t)} \ \ \ \ t = 1, \ldots, s \notag  \\
            & p \ge 0 \notag \\
            & \alpha \ge 0 \notag.
        \end{aligned}$$

Here $\sigma$ denotes the random permutation of the columns of the LP. We use ${\ensuremath{\textrm{OPT}}}(s,\delta)$ to denote the optimal value of $(s, \delta)$-LP and ${\ensuremath{\textrm{OPT}}}(s)$ to denote the optimal value of $(s, 1)$-LP.

The static pricing algorithm [<span style="font-variant:small-caps;">OTP</span>]{}of [@agrawal] can then be described as follows.[^2]

1.  Wait for the first $\epsilon n$ columns of the LP (indexed by $\sigma(1), \sigma(2), \ldots, \sigma(\epsilon n)$) and solve $(\epsilon n, 1 - \epsilon)$-Dual. Let $(p, \alpha)$ be the obtained dual optimal solution.

2.  Use the classification given by $p$ as above by setting $x_{\sigma(t)} = x(p)_{\sigma(t)}$ for $t = \epsilon n + 1, \epsilon n + 2, \ldots$ for as long as the solution obtained remains valid. From this point on set all further variables to zero.

Note that by definition this algorithm outputs a feasible solution with probability one. Our goal 