Abstract As publishers gather more information about their users, they can use that information to enable advertisers to create increasingly targeted campaigns. This enables better usage of advertising inventory. However, it also dramatically increases the complexity that the publisher faces when optimizing campaign admission decisions and inventory allocation to campaigns. We develop an optimal anytime algorithm for abstracting fine-grained audience segments into coarser abstract segments that are not too numerous for use in such optimization. Compared to the segment abstraction algorithm by Walsh et al. [2010] for the same problem, it yields two orders of magnitude improvement in run time and significant improvement in abstraction quality. These benefits hold both for guaranteed and non-guaranteed campaigns. The performance stems from three improvements: 1) a quadratictime (as opposed to doubly exponential or heuristic) algorithm for finding an optimal split of an abstract segment, 2) a better scoring function for evaluating splits, and 3) splitting time lossily like any other targeting attribute (instead of losslessly segmenting time first).