Patent ID: 8719096

Claim:
A computer system for providing online advertisements, comprising: a server comprising a processor device, an input/output interface, and memory, said server configured to perform: receiving a query comprising a keyword; obtaining from a data store: bids from bidders in an online advertising auction, said bids for displaying advertisements, wherein said bidders are associated with the keyword; click-through rates for advertisement positions on a web page; and utility factors associated with the advertisement positions in a slate of advertisements; using dynamic programming to recursively evaluate a utility of subslates of the advertisements in order to generate a maximum utility slate of the advertisements for the keyword, using a plurality of the bids, a plurality of the click-through rates, and a plurality of the utility factors; wherein the maximum utility slate of the advertisements comprises a maximum number m of advertisement positions; placing the advertisements from the bidders in the advertisement positions within the slate of advertisements; padding any empty positions at an end of the slate of advertisements with dummy bidders to produce the maximum utility slate with exactly the maximum number m of the advertisement positions; initializing the bids of the dummy bidders to a minimum bid amount; initializing the utility factor of each dummy bidder to zero; and outputting the maximum utility slate of advertisements; and an advertisement store storing the slate of advertisements for the online advertising auction.