---
abstract: |
    We consider packing LP’s with $m$ rows where all constraint coefficients are normalized to be in the unit interval. The $n$ columns arrive in random order and the goal is to set the corresponding decision variables irrevocably when they arrive so as to obtain a feasible solution maximizing the expected reward. Previous $(1 - \epsilon)$-competitive algorithms require the right-hand side of the LP to be $\Omega (\frac{m}{\epsilon^2} \log \frac{n}{\epsilon})$, a bound that worsens with the number of columns and rows. However, the dependence on the number of columns is not required in the single-row case and known lower bounds for the general case are also independent of $n$.

    Our goal is to understand whether the dependence on $n$ is required in the multi-row case, making it fundamentally harder than the single-row version. We refute this by exhibiting an algorithm which is $(1 - \epsilon)$-competitive as long as the right-hand sides are $\Omega (\frac{m^2}{\epsilon^2} \log \frac{m}{\epsilon})$. Our techniques refine previous PAC-learning based approaches which interpret the online decisions as linear classifications of the columns based on sampled dual prices. The key ingredient of our improvement comes from a non-standard covering argument together with the realization that only when 