Patent ID: 8799082

Claim:
A computer-implemented system that allocates advertisements to ad-slots, comprising: a memory; a processing unit coupled to the memory; a blended schema that incorporates properties of both a primal-dual schema and a dual-fitting schema, the blended schema simultaneously maintaining feasible duals and bounded duals for individual iterations, wherein: a property of the primal-dual schema that is incorporated into the blended schema includes maintaining the feasible duals for individual iterations; and a property of the dual-fitting schema that is incorporated into the blended schema includes maintaining the bounded duals for individual iterations; and a matching component configured to be operated on the processing unit to match an ad slot offered by an ad host to an ad from an advertiser based at least in part upon the blended schema under a relaxed assumption that a bid from the advertiser is negligible compared to an advertising budget of the advertiser and is to be ignored.