- 1/e$. The competitiveness of the algorithm of [@Devanur11] under the permutation model is still unknown and was left as an open problem by the authors.

[*Our results.*]{} Our focus is to understand how large $B$ is required to be in order to allow $(1 - \epsilon)$-competitive algorithms. In particular, the requirements for $B$ in the above algorithms degrade as the number of columns in the LP increases, while the the lower bound does not. With the trend of handling LP’s with larger number of columns (e.g. columns correspond to the keywords in the ad allocation problem, which in turn correspond to visits of a search engine’s webpage), this gap is very unsatisfactory from a practical point of view. Furthermore, given that guarantees for the single knapsack case do not depend on the number of columns, it is important to understand if the multi-knapsack case is fundamentally more difficult. In this work, we give a precise indication of why the latter problem was resistant to arguments used in the single knapsack case, and overcome this difficulty to exhibit an algorithm with dimension-independent guarantee.

We show that a modification of the [<span style="font-variant:small-caps;">DPA</span>]{}algorithm from [@agrawal] that we call *Robust [DPA]{}* obtains 