goal is to obtain a feasible solution while maximizing its value. We use ${\ensuremath{\textrm{OPT}}}$ to denote the optimum value of the (offline) LP.

By scaling down rows as necessary, we assume without loss of generality that all entries of $B$ are the same, which we also denote with some overload of notation by $B$. Due to the packing nature of the problem, we also assume without loss of generality that all the $\pi_t$’s are non-negative and all the $a^t$’s are non-zero: we can simply ignore columns which do not satisfy the first property and always set to 1 the variables associated to the remaining columns which do not satisfy the second property. Finally, we assume that the columns $a^t$’s are in *general position*: for all $p \in \mathbb{R}^m$, there are at most $m$ different $t \in [n]$ such that $\pi_t = p a^t$. Notice that perturbing the input randomly by a tiny amount achieves this property with probability one, while the effect of the perturbation is absorbed in our approximation guarantees [@DevanurHayes09; @agrawal].

Applications {#applications .unnumbered}
------------

Write about applications on online revenue management and resource allocation (like ads) to motivate the problem.

[*Related work.*]{} The random permutation model has 