  Motivated by the problem of optimizing allocation in guaranteed display
advertising, we develop an efficient, lightweight method of generating a
compact {\em allocation plan} that can be used to guide ad server decisions.
The plan itself uses just O(1) state per guaranteed contract, is robust to
noise, and allows us to serve (provably) nearly optimally. The optimization
method we develop is scalable, with a small in-memory footprint, and working in
linear time per iteration. It is also "stop-anytime", meaning that
time-critical applications can stop early and still get a good serving
solution. Thus, it is particularly useful for optimizing the large problems
arising in the context of display advertising. We demonstrate the effectiveness
of our algorithm using actual Yahoo! data.
