  We present prior robust algorithms for a large class of resource allocation
problems where requests arrive one-by-one (online), drawn independently from an
unknown distribution at every step. We design a single algorithm that, for
every possible underlying distribution, obtains a $1-\epsilon$ fraction of the
profit obtained by an algorithm that knows the entire request sequence ahead of
time. The factor $\epsilon$ approaches $0$ when no single request
consumes/contributes a significant fraction of the global
consumption/contribution by all requests together. We show that the tradeoff we
obtain here that determines how fast $\epsilon$ approaches $0$, is near
optimal: we give a nearly matching lower bound showing that the tradeoff cannot
be improved much beyond what we obtain.
  Going beyond the model of a static underlying distribution, we introduce the
adversarial stochastic input model, where an adversary, possibly in an adaptive
manner, controls the distributions from which the requests are drawn at each
step. Placing no restriction on the adversary, we design an algorithm that
obtains a $1-\epsilon$ fraction of the optimal profit obtainable w.r.t. the
worst distribution in the adversarial sequence.
  In the offline setting we give a fast algorithm to solve very large LPs with
both packing and covering constraints. We give algorithms to approximately
solve (within a factor of $1+\epsilon$) the mixed packing-covering problem with
$O(\frac{\gamma m \log (n/\delta)}{\epsilon^2})$ oracle calls where the
constraint matrix of this LP has dimension $n\times m$, the success probability
of the algorithm is $1-\delta$, and $\gamma$ quantifies how significant a
single request is when compared to the sum total of all requests.
  We discuss implications of our results to several special cases including
online combinatorial auctions, network routing and the adwords problem.
